Recently, we experienced significant slowdowns on a WordPress site we have had running for about a year and a half.
Investigating, we found that our database for the site had grown to 500,000+ lines of entries. Of those, 300,000+ were in the postmeta table.
Obviously, we needed to clean that out. We began by eliminating 'revisions' of posts. That helped a little, but not much. In reading the WordPress Codex, we found that plugin and theme data is also stored in that table. Problem is, there isn't any intuitive way to remove all the entries for plugins and themes that have been removed previously. (It was obvious to us that the authors of those plugins and themes appeared to have no interest in writing uninstall modules for their offerings. The entries are scattered throughout the table and don't follow any rhyme nor reason.)
So, might I suggest, that in a future rev of WordPress, maybe new tables, one (or a set) for plugins another for themes, become a WordPress standard, and the criteria for those products be that they be written to use the new tables.