It's amazing what a difference Xen makes (with memory)
When Linode recently bumped up their memory offerings (and therefore prices for a comparable system went down), I decided to jump to the beta Xen hosting, knowing Xen allows swap space to be allocated (which OpenVZ does not). I figured that, even if my system was going to flirt with running out of space, at least swap would save my daemons and permit things to keep running. I was not disappointed.
Much to my surprise, despite being an almost identical system, the free memory reported on the Xen Linode system is completely incomparable with the old OpenVZ version. I've actually added several daemons (fail2ban, dkim-milter, policyd-weight, and even bind9) and upped some of my configuration allotments, and my system has still never even touched the swap space. In fact, according to 'free' the system is only using ~250m with the remainder going to buffers and cache.
I don't know what it is about Xen vs OpenVZ that makes the memory consumption so dissimilar, but based on this direct comparison I would recommend everyone in the vps market to test a Xen node for their systems. It's just astonishing how much more you can pile on the Xen memory model and keep things running smoothly and safely. And as far as I can tell, Linode has easilys one of the strongest and most cost-efficient offerings in this field, with excellent support and a superb control panel to boot. I'm currently loving my Xen Linode, and I don't plan on having to move elsewhere any time soon.
With today's multi-core multi-gigahertz CPUs I don't think the overhead is that significant. And as you have said, the memory management/accounting model on OpenVZ just feels so broken. I won't put a production site/software on a VZ box without a HUGE leeway on their "burstable memory" as you never know when one of your app is going get NULL in malloc() although there "appears" to be plenty of memory around…