Server advice needed: multisite/buddypress

I keep getting out of memory errors on my Multisite/buddypress installation. I've worked with my host, but they are constantly asking me to upgrade and for more money. I'm currently paying $100 a month for their version of an 9 node VPS. - I'm not at the point financially that I'm able to upgrade to their recommend $150 a month dedicated server.

It seems like a lot of power to me but I'm not being told that I should transition the site to dedicated server because my database in nearing 2000 tables and the (it's actually at about 1600 right now) and that wordpress multi with my plugins and caching is pretty resources intensive.

My network is up to about 140 subsites and about 380 members. Not all the sites are active, but they contribute to the size of the database. I keep the database optimized and cleaned up by deleting spam sites regularly.

Does this sound right to the rest of you guys, what kind of performance should I be getting out of a VPS. Can VPS handle a multisite of this size?

I really need advice on this, am getting taken by my hosting company?