OpenClipboard Failed (HRESULT: 0x800401D0) after a series of copy/paste via Excel Interop

I have an Excel VSTO add-in which copy/pastes shapes from one source worksheet to a destination worksheet (both in same workbook). The destination worksheet contains data entries (one row per entry). A routine performs the following, for each row:

1. Get data
2. Calculate X-Y position based on data
3. Copy shape from source worksheet (shape name depends on data)
4. Paste shape in destination worksheet
5. Move to calculated X-Y position

The routine works fine on my two testing computers for up to 300 rows (did not try for more). A client is having problems with all their computers, for "large" data tables. The code breaks at some row between 100 and 130, but to a different row each time the same routine is run on the same file (it is kind of random).

OpenClipboard Failed (Exception from HRESULT: 0x800401D0 (CLIPBRD_E_CANT_OPEN))

at System.RuntimeType.ForwardCallToInvokeMember(String memberName, BindingFlags flags, Object target, Int32[] aWrapperTypes, MessageData& msgData)

at Microsoft.Office.Interop.Excel.Shape.Cut()

at ExcelAddIn.MyCode

I believe the routine breaks at step 4, and suspect the clipboard stack might get overwhelmed? I read here this HResult may refer to race conditions, but in my case we are trying to cut, so the shape is not yet inside the clipboard.