Q, not a thought. Granted, I just read your post.
Without stripping out the entire code for it, and really munging things up, I have no idea at the moment.
Mod_rewrite, in it's purest form, should be able to take /this/that/ and turn it into whatever from the database. It can, but then you get into things like permalink style and mixed variables. Someone wants /%category%/%postname%/, someone else wants /%postname%/, some other Joe wants /%category%/%postname%.html and so on.
Working on a side project at the moment, and just happening to be in the area of permalinks at the moment, the solution we came up with for our need was this:
pages: /pagename/
articles: /articles/category/title/
news: /news/category/title/
etc.
That works for our uses, but obviously not for WP, or MU. Our whole structure essentially relies on the first /value/. We're keeping an array of values to check against (articles,news,downloads,etc), and then if nothing matches we look for a page with /value/ as its slug (filename, or whatever).
But, since most WP users out there blog with pages as a second thought, that approach won't work.
Looking at my own rewrite rules for my blog, I see a lot of extra stuff, like attachments for every page type of rules, etc.
IMHO, they look mostly unnecessary, unless there would be an attachment associated with that page, but I'm not going to say they are. I just haven't dug up much on it.
However, I will confirm and agree that blogs with pages process slower. Visually they don't appear to, although I don't have a blog with more pages than my own at the moment (about 20-30), so it's tough to say for me.
What's the real difference for pages anyway? At a very fundamental level, nothing other than the default page template and the fact that by default the links to them generated by WordPress don't have /category/ (or whatever) added to the front.
To me, completely rethinking pages, to make them posts but simply with a different template, would probably be something to consider. The only real thing to look out for would be sub-pages, but still it would seem that initially looking up category names and comparing to /value/, and then looking at page slugs if nothing found would be an option.
As long as a page and a post can't share the same slug, there shouldn't be a problem. IMHO, I'd rather do 4 small, additional reads from the db (OK, actually it would be more like 2 as they would be stored possibly, or whatever) than have to process that large of a rewrite chunk.
I wonder if WordPress.com has that issue, and what's has been considered. With all the users they have, I can't believe that one of them doesn't have a ton of pages.