WordPress VPS out of Memory Problem

First and most important question – did your host meant that you server is actively sending spam or is being used to relay spam? If former then you need to trace that down and cleanup (which takes someone competent looking at it, if you are not confident to do it yourself).

After that my first suggestion would be to install caching plugin (W3 Total Cache is currently one of the most popular). If that is not enough to bring resource consumption under control you are up for profiling internals of your WP install (with tools such as xdebug or xhprof) and possibly tweaking web server stack.