For our conversion, I ran Xenu's Link Sleuth against the site to gather all the URLs on the site and exported it to a file I then imported into MS Access for processing.
I then purchased Scott Belosavich's URL Rewrite Import/Export module, did the full export to find the fields necessary for import, aligned this with the table I had and then generated all the redirect to links, set them all to be permanent 301 redirects per the field setting for that.
The import into Magento's core_url_rewrite index was uneventful and the 301s immediate for Google. For product pages that did not directly match, I set redirects to the nearest category so people had a general idea where to start.
Aside from the usual cringing white knuckle wait with the anticipated drop in traffic, between the sitemap and the redirects, Google was pretty quick in getting things changed over.
You also might use your Webmaster Tools account to mine ancient incoming links to see where product still exists despite the 5 year old 404 Google's been throwing and re-link to the appropriate new pages. We recovered about 20 rather good backlinks this way.