If you said the actual size of db isn't too big, but the number of equerries are overwhelming then may be it is Vbulletin's code not being too efficient or rather to say it treats the SQL db mercilessly like a beast.
In this case there may be a solution using RAMFS approach.
Assuming SQL db is 2-3GB and yr RAM is at least 8GB, your CPUs got at least quad core Opteron or Xeon, mount a RAMFS on a mount point and copy the SQL db in there. It should be lightning fast to generate answers to Vbulletin's queries, these are mostly SQL 'select' commands, which in binary terms are intensive binary searches.
In this method you are basically running RAM-DISK.
http://www.linux-mag.com/id/7689
But your better have a corntab job dumping (e.g. mysqldump function) that SQL out e.g. hourly to actual HDD which has daily backup. Otherwise of OS hang or power blackout then doomed is your db.
I have no idea weather yr server offer you KVM over ip, aka if you can get a remote X session to it. If so your resource meters would tell you how busy is your physical HDD. The more is physical HDD being busy the more the RAMFS approach will make a huge difference.
RAM can be added in dedicated servers at some $$$$
But when using, be sure your allocation is sufficiently more than the size of your SQL db.
It hangs and lost data when db grows out of allocated space.
For co-location deals I think RAM is only one time cost with a setup fee, that is they power off your box and add RAM for you. For rentals deals there is monthly fees ranging from US$4 to $30 /month per GB.
I think you know all these deals and you know about RAMFS.
Give it a try!
