My experience has been different. On my 768MB openvz VPS bitcoind kept getting killed due to out of memory conditions. So I think you need 1-2GB just to be safe.
How often does it crash? My 512mb ubuntu VM is stable for at least 12 hours at 65% mem usage. Swap space is barely being used.
If you are worried about your data not being safe you can get a KVM VPS and encrypt the filesystem that holds the wallet and bitcoind.
LOL
If someone has physical access to your server, you're not safe
If someone has root access to your server, you're not safe
If someone has hypervisor to your server, you're not safe