I do a drastic spring-clean about every 12-18 months. I export my blogs, install a new
WP, import the old blog, then start testing and benchmarking. My essential custom functions are always in their own custom functions file, making them easy to call into any theme through an include in the theme's functions.php. This goes in first & performance checked. Then I install and test each plugin, looking at speed and performance. Once those are tested, my theme goes in. By this stage, I have a really clean database and have pinpointed where there are any performance issues or slow queries.
I used to do regular spring-cleans the way Jeffro does but found that by the time a blog has gone through several updates and plugins have been changed and/or updated there was just so much rubbish left behind in the database. Plugins are really bad at leaving things behind (on one site, I just found a cron job running that has been running for two years after the plugin had been deleted!)
It's a bit of extra work to do a major cleanup like this but its always resulted in performance gains so I keep doing it.