Hi everyone,
Once again everyone seems to think this is a VM issue. I'm sorry to say, but it isn't. Don't blame VM, blame Joomla!. That's what's causing the session issue.
Everyone knows that VM is built on top of the Joomla! framework. Setting the session storage to none rather than database should fix the problem. Beyond that it could be a server/machine issue as Milbo pointed out. If the session handler configuration doesn't work for you, the next step is to consult your hosting provider.
But ultimately, please remember the separation between Joomla! and VirtueMart. Joomla! affects VirtueMart, but not the other way around.