Hello,
We don't have any information about some incompatibility between AdminExile and JoomSEF.
According to your examples the incorrect URLs have a form of SEF URLs generated by default Joomla router, so most likely your Active Handler for VirtueMart was changed on JoomSEF's Manage Extensions page.