Joomla 2.5.16
Virtuemart 2.0.26
JoomSEF 4
Virtuemart extension

This is an upgrade from Joomla 1.5
23,000 URLs were imported via SQL

There are two problems
Imported URLs do not work. e.g.
/index.php?option=com_virtuemart&category_id=622&page=shop.browse&Itemid=10622

Configuring JoomSEF to create new URLs places an ID (instead of virtuemart) into the SEF, e.g.
/31/category/product

Hi,

It is not that simple to import old URLs from Joomla 1.5 to 2.5, as they both use very different URLs structures. If you used VirtueMart 1.x on your Joomla 1.5 website, the URLs are completely different., you would have to write some migration script to fix their structure.

For the ID in your SEF URL, first of all check what is your Active Handler set for VirtueMart extension in JoomSEF's Extensions Manager. Then check your menu alias, if it is set correctly.

That is disappointing.
I understand this is not your issue but a problem for virtuemart.
To my amazement, I have found no solutions on virtuemart forum, so I wrote a small script to modify the database.