There's usually a problem with VirtueMart when you use more than one menu item for it, because it doesn't set the Itemid correctly for the links. Try disabling SEF in Joomla's Global Configuration and check whether all the links on your website contain the Itemid variable and work correctly. In that case it should be possible to set up JoomSEF to work correctly with VirtueMart.
We can also check your website for you and try to configure JoomSEF as a paid support service. If you're interested, purchase 1 hour of our support time at: www.artio.net/e-shop/support-services/joomla-support-1h