I have been facing the same issue with over 16000 posts and have seen the performance of my site degrade. But I just put in a solution that did the trick. My initial load query is down from 6.8s to 0.4 seconds and the heaviest category lookup has come down from 4.3 seconds to .4 seconds as well.
You will have to edit [wp-includes/classes.php] file
Look for the line
$request = " SELECT $distinct * FROM $wpdb->posts $join WHERE 1=1" . $where . " GROUP BY " . $groupby . " ORDER BY " . $orderby . " $limits";
And replace it by
$request = " SELECT * FROM $wpdb->posts $join WHERE 1=1" . $where . " ORDER BY " . $orderby . " $limits";
That basically removes the unnecessary DISTINCT on ID which is a primary key in wp_posts table anyway and cannot be duplicated. The distinct and group by are the real killers.
Atul Bansal (http://www.sahihai.com)