We had the same issue moving our site from nopcommerce to magento. The structure of the site in regards to category and even file extension (.aspx to .html) changed. We had over 2000 products and to create redirects for all of them was quite a bear.
What we ended up doing was to look into Google's rankings of our top 500 pages and focus on getting those redirected initially. Checking both the supplemental and primary indexes helped us to figure out which ones to do. I also ended up using excel and its formulas to create the redirect links enmass and then copied them to my .htaccess file. Also too, if you had a specific directory where your ecommerce site use to be located ( we had /Store/) create that directory and place your .htaccess in that file with Symlinks turned On.
This seemed to take care of everything for us and helped us to focus on links that were actually indexed.
