What do the old URLs look like and what do the new URLs look like?
You need a rule that matches requests for old URLs and then does something with those requests.
If everything in the new URL can be derived from what is in the old URL request then you can build the new URL and issue the redirect entirely within the rule.
If there are elements in the new URL that are not in the old URL you will need a different approach. Rewrite the request to a new PHP script. This new PHP script will be only a few lines long. It will grab the extra elements for the URL from the database, build the new URL and issue the redirect.
I don't understand why you're currently trying rules that redirect old URL requests to a URL format that uses parameters. At worst, you're creating duplicate content problems. At best, you're creating a redirect chain. // EDIT // OK. Removing the R=302 stops the redirect and turns it into a rewrite. This is likely closer to what you need. If you ask for URLs with parameters, does the new PHP script then redirect the request to the new URL format that the new add-on uses?