I think your first problem is that you are using a VPS. You should never use a VPS in a high load situation like this - buy a dedicated server! They only cost about $70/month, which you should be able to afford if you have a successful site. Ideally you should get as much RAM as you can afford and/or an SSD drive.
I know you said you didn't want to throw hardware at the problem, but there are limits - you can't run a massive database on crappy hardware and expect it to work smoothly.