Yup, had same problem with my server (im not submiting galls, but mysql was killing me). I hired someone to optimize my server for me. It cose my only $75, and it has worked wounders for me. Server is 10x faster than it was before and handles great. I recommend this guy below and tell him you're problem. He will optimize the server for you're needs.
AIM :
Vintage Support
Good luck.

Also you might want to upgrade to 1gig ram.