You're well out of the comfort zone, through the discomfort zone, and halfway through the having-a-hot-poker-shoved-up-your-backside zone :-)
You should really be thinking of the toolbar as a speed-bar, somewhere where the user can go to do common operations with minimal actions. Other than the Gimp with its infamous UI, I can't fathom any application that would need anywhere near 1,000 common operations worthy of use in a speed-bar.
Perhaps you need to rethink what you're providing.
Some of the Microsoft applications do it reasonably well, they divide their toolbars into sections (e.g., drawing, statistics, formatting) and let the user decide which sections are shown. That way the user decides if they want a minimal workspace or whether they want the whole top half of their workspace taken up by toolbars.
The non-common operations should always be available by menus anyway, whether common is fixed by you (hard-coded), chosen by the user (configuring those sections) or "intelligently" shown by the program (based on previous use).
Here's what I would consider a good approach.
Have all operations accessible from the menus by dividing them into sections (operations within a section should be at least vaguely related). Let's assume for now you can have 30 sections of 30 operations each (unlikely, I know, but simple for this discussion).
Have a special section for adaptive operations. By that, I mean a section the program will populate with operations based on how often the user uses them. To do that, you need to keep a record of how many times an operation is used by the user (each user has their own count, of course, since their usage profile will be different).
Allow the user to configure which sections are displayed in toolbars, including the adaptive one. This gives them control over it.
The adaptive section should be populated by the most commonly used operation provided they don't already appear in another toolbar already. That way, the user can get at the most commonly used operations which aren't already on one of their chosen toolbars.
That seems to me the most flexible solution, giving the user total control over the use of their screen real-estate.