I just posted this on another thread, so apologies for being a bit "spammy" but I think it's still relevant to the question.
I highly recommend trying out one of the Joomla SEF plugins.
We use (and love) AceSEF with the Virtuemart extension.
http://www.joomace.net/The base software is free (with a backlink at the bottom of each SEF-served page), but the Virtuemart extension is $15 or something. Seriously, it's worth every cent.
The best part for us after migrating from an old site, we had the ability to very easily see which pages were generating 404 errors, and redirect them to the correct virtuemart page.
@augr, You mentioned that you had issues with it breaking something important? I've had no such issues with my site, but I did have to create a few (like 3) custom URLs to handle a few fancy redirects that I wanted to do. Nothing major, and certainly nothing that was broken beforehand.
What broke?
Tim