In practice this mean that Linode offers 512MB RES/RSS memory (+swap) and Edis offers 512MB VIRT memory.
VIRT memory limiting is very a serious issue for some software. For example, apache may use 10x VIRT memory because it is threads-based (most linux'es reserve about 6-10M VIRT memory for the stack of each thread). VIRT memory is usually considered "free to allocate" and software (JVM, soft that uses mmap and so on) is written with this assumption. But this is not the case with OpenVZ VPS servers. Just run "top" to get an idea about VIRT and RSS memory usage of common programs.
It is exciting how this issue is not well-known. I even think that 91.318% of "apache is memory hungry" things (they are still partially true, but..) came from OpenVZ VPS benchmarks.
So in my opinion 20$ 512MB XEN is way better than 10$ 512MB OpenVZ because 512MB XEN is very different from 512MB OpenVZ.
P.S. my knowledge of OpenVZ may be outdated because I moved from OpenVZ VPS servers a couple of years ago.
host level (para)virtualization vs. os level virtualization. The latter allows significantly increased density while the former enjoys much better isolation, customization and usually* more reliable resource reservations.