Hm, that gave me an idea, I am now testing openjdk-7-jre-headless package on a 512 mb vps
That's what I'm using on my node. It works, but eventually the heap will be full due to leaks. On a 512M, you should keep the max number of connections low.
Haven't tried the Oracle SE VM yet. I'll have a go at that later.
I never thought about testing it.
We have to make it run smooth on 512 Mb, and if -headless JRE helps with garbage collection better, then it should be the default java install for NXT. I'll update my guide with that info, after a few hours of testing.