I had (and am still somewhat having) the same problem as you. I was running a shared hosting account with DreamHost with several WP blogs and got the dreaded 500 error so they said I should go with VPS, I did and during the first free trial week (you can set memory to anything you want the first week so you can figure out how much you need) everything was going well with my memory usage below 150M.
Then all hell broke loose with runaway memory useage. The memory use went over 4,000M compared to 150M the previous five days. Disaster and my VPS came to a crunching halt. I had to go in via SSH (using my terminal.app in Mac OSX) to see in real-time memory usage.
I shut down the WP sites that weren't really being used, I disabled all plugins and did this to get my main site http://www.hawaii247.org back up and running. Strangely even though I had enough memory I couldn't get the site going again. Finally it magically started working again, I could get into wp-adim (I set-up my front page as a static html so it wouldn't tax the server).
I slowly added necessary plugins to get the site back to where it was before, I disabled other plugins that might cause the load. DH kept saying it was wp-cron doing much of the memory load along with the fetching of my tag files.
I'm back up and running again but it was terrible, on the weekend so tech support wasn't very fast (at least not in internet terms). My site was down for almost 24 hours.
I'm doing some other things to alleviate server load which may or may not work.
* I turned on php cache (xcache) and have mod_php version 5.x running
* I incorporated a Google AdSense search onto the site instead of using the built-in search which would generate all the posts in the results.
* Set up the plugin HyperCache to cache pages
and a number of other things.
I can now see that having tags on the site hammers the memory usage when people hit the tag to generate results. I'm considering just stopping the use of tags.
In the DreamHost VPS info it says just having the server running uses up about 100M of memory so you'll have to figure on your site using above and beyond that. Their shared hosting plans have a cap of 90M per account.
Did you ever get your memory problem resolved?