I think I may be onto something...
When I disabled the virtuemart main menu item that linked to my the shop category, and instead installed the virtuemart module (mod_virtuemart), a few differences are notice:
(btw, I purged all existing again after making that change, then refreshed the page)
- the SEF link to the category (based on it appearing in the module rather than the menu) is now "home/2009-collection" (I assume it picks "home" to append to since there's no virtuemart menu item anymore)
- the "Show Cart" link in the cart module is no longer replaced by a SEF URL (its just the standard "index.php?page=shop.cart&option=com_virtuemart&Itemid=1")
- every product SEF URL is now "home/<productname>" instead of "category/<productname>"
- the "previous/next" product navigation links are now all getting the correct SEF URL
Most interestingly, the Prev/Next links and Show Cart link break again the moment I enable that virtuemart menu item.
Does that give you a hint as to what is going wrong?