I'm having a similar issue. I'm testing out VM1.1 with Joomla 1.5 using Artio JoomSEF (Free version) with the VM 1.1.3 Extension.

All URLs are properly being SEF'd except subcategories. The interesting thing is, if you hover over the link it shows the properly SEF'd version of the link in the status bar of the browser, but when you click on the link, the address bar shows the non-SEF'd version.

I've tried a purge of SEF URLs but same issue. Also, I ensured that my flypage settings in the VM Ext are set to show SEF'd links for flypages.

Looking for input. (I realize that VM 1.1 is not yet a stable release for Joomla 1.5).