I had persistent issues with the db while running the 3.0.x version of vBulletin...upgrading to the 3.5.x version helped somewhat....
switching to a dedicated db server fixed it immediately. I also keep all the other softwares up to date as well (ie: php, mysql, etc) and request reconfiguration adjustments thru vB regularly.
3.0.14 is the current version IIRC, just released this week...that may also be an issue, and I would definitely be concerned about the security of the software/db - I know of one other TLCA forum that was recently hacked, possibly due to their out-of-date IPB forum.
course, you have under 10,000 posts...'MUD regularly generates 2500-3300 per day...however, the db slowness isn't likely the result of size but of tweaks and settings. (unfortunately, things a "normal" webhost won't play with)