Hi all,
well, first of all I have to explain one thing - we have investagated this very closely and this is NOT really the plugin issues.
The problem is following:
If you use the VM category option when creating a link in men, the item in menu contains only Itemid information and nothing else. The rest of parameters is handed over as parameter of the menu item, which JoomSEF in general does not understand, because it only works with URL.
(this could be fixed by rewriting the XML definition for the VM view parameters, by telling Joomla not to hand over the parameter via params, but to use URL instead -- this change would need to be done by authors of VM)
The other solution is to make the links in the menu by entering the correct URL directly, which will include the needed parameters - namely the category_id.
We also plan to revise this and add possibility of loading the menu item parameters when not submitted by VM, but that will require additional queries to DB and thus may increase the overall consumption of resources.