If I am understanding you correctly, you are doing mod re-writes to help with your SERPs because your site uses javascript. Then you state that "Now we see that we were not correct.".

You were correct. Spiders cannot follow javascript links. You can however remedy this with use of CSS navigation, but it looks as if you are using a product cart of some sort though. There are product carts that use CSS navigation, but they still use the dynamic URLs. The best way around this is to do as you suggested and implement URL re-writes. It will take some time if you have alot of pages, but is well worth it in the end.

As far as the duplicate content is concerned "incrediblehelp" is right on...

"I dont think you need to ask for reinclusion just eliminate the duplicates from the website and then ask for removal of the duplicates through Google Webmaster Tools."

Hope I understood you correctly. If so I hope this helps some. - Saxman