Hey all - I recently had a project for a client in which I needed to populate the menu with about 970 individual entries. Obviously constructing such a menu by hand was out of the question.
Digging into the core, I found that there were absolutely no hooks where I needed them to be. In the end, I managed to throw together a plugin based on the core menu code that allows you to populate a sub-menu with items as selected with standard WP_Query parameters. Currently, enabling the functionality on an item requires that you create a custom menu item, then find it in the database and add about four fields or so.
Specifically, you call the plugin's version of wp_nav_menu instead of the default one. The difference is that the plugin's version is watching for a new type of menu item. When it encounters a menu item of said type, it executes a query based on the query parameters attached to that item, generates fake menu item objects for every returned post, then inserts them into the original menu item object list before sending it off to the function that generates the actual markup.
I tried implementing a few different forms of auto-caching, as well. JSON files, database entries, serialized text files and WordPress Options, all of which would check for changes and re-gen if necessary, but all of them really just seemed to slow things down rather than speed 'em up. Ideally, the system would cache the generated markup rather than the menu item objects themselves. Even with 970 items, though, there doesn't seem to be too big of a performance hit when caching is turned off.
The thing is essentially a massively fat hack, though. It's pretty much the equivalent of me making a copy of the core code then stumbling around half-blind with a broadsword smashing random chunks until it worked. One notable side-effect is that using it totally messes up the WP menu-order numbering (not that I really ever found much use for it though).
If there's enough interest, I'll set about polishing it up and throwing together an admin screen for the thing - or at least write a blog post on the topic sometime soon.
I don't think I'll be submitting it as a patch to Trac anytime soon, though - like I said, thing's a mess! O.o