You will be fine with 512 ram.
Im ok with 384 ram.. And even at a day i had 7000 visitors, server loads where below 0.3 all the time.

Try this host: http://byethost.com/vpsplans
Im with them for the last 3 years, 110% satisfied.. (Not offshore, stay legal and you will be cool.)