Have you tried adding caching? It may help as it lowers the number of requests you server has to deal with. If plugins are the cause then this may not help at all. It is worth trying before you spend more money.
You may decide to switch hosts that are more helpful. Or you may look at Amazon's S3 hosting.
It may well also be that you get traffic spikes and the concurrent connections are eating the memory. Cashing may help with this but you may also have to add more RAM.
Was there ever a time were you didn't have overages?
Can you let us know how much RAM and the speed and number of processors are currently on the server?
Also, can you list the names of your must have plugins. Knowing this may draw responses from other members regarding less memory intensive yet similar plugins.