There appear to be two possible reasons for this:
1) My permalink structure (I like %postname% or %category%/%postname%) sucks. Apparently having the category name in the permalinks will induce a performance hit when a WP site has a lot of content (and I'm over 3,000 posts and attachments).
2) Something to do with the recent change to Options +FollowSymLinks. My site went down a couple of weeks ago and was only restored when a my hosting rep commented out this line in my .htaccess. I read elsewhere that WP needs this to be turned on for permalinks to work correctly. I don't know why permalinks would be working at all if this isn't enabled though.
Some useful dialogue from wp-testers list:
Also this trac ticket:
And some metrics--permalink structure vs length of the rewrite field in wp_options:
SQL statement to test this yourself (from the trac ticket): SELECT LENGTH(option_value) FROM wp_options WHERE option_name LIKE 'rewrite%'
There are some competing assertions here... some say that large rewrite rules should be no problem as long as the max query size for database requests can accommodate. Might this be something that could be tweaked to resolve these issues?
Now here's the kicker: when I switch to a clean permalinks style with a corresponding 100 fold decrease in rewrite value length... nothing happens. The query to wp_options still drags as much as before.
Any ideas? Maybe I'm barking up the wrong tree.