I have an custom control, defined in class library that dynamicly constructs context menu, and makes "Paste" item visible only if there is any text at Clipboard (..GetDataPresent(..)).

Main function is attributted as STAThread, but when void of Menu forming is calling it cause following exception:

"You must set STA threading model for making OLE calls, check that your "Main" function is marked as STAThread"
Call stack shows that this exception was raised at checking clipboard part of void

For additional:
1. Calling Clipboard methods from menu (Copy, etc) does not raise any exceptions
2. The form with this control worked properly in test application (that simple loads this form), no any problem with STA and OLE (in target application form hosted by an object that included into Window Service and called remotly by TCP Channel)

I wonder if OLEInitialize isn't getting called for some reason...  So, the Main method of the application in which this control is being hosted is marked with STAThread?

Of course, all "Mains" marked as STA

At what stage in the execution of the program are you building the menu?  Is this in, for example, the Popup event?

Yes it is, the Popup event

Have a look at what threading state Application.OleRequred() returns you....