We finally found time to investigate this issue.
Let me start by clarifying that yEd does not lock the system clipboard at all. However, yEd does check for clipboard content changes. As far as I can tell, doing so does not violate any operating system coding guidelines.
However, when moving multiple cells in Excel, Excel sometimes (but not always) copies an image representation of the moved cells (and their content) to the system clipboard. Since this changes the clipboard's contents, this copy operation triggers the check in yEd. As part of the check, yEd tries to determine if the clipboard contains image data. The check for image data seems to trigger the Excel notification "There's a problem with the clipboard, ...".
Given the above information, we believe this to be an Excel problem. Excel not always performing the copy operation is also a strong indication to us that something is not working as it should in Excel (otherwise moving cells would either always copy an image to the system clipboard or never).