Thank you Ryan. I didn't think of formulating my google query this way. The solution though was found yesterday and it appears to be very simple. I tryed to remove my redirect rules one after another. So that if originally I had:
redirect 301 /old/ http://www.mysite.com/new.php
redirect 301 /old/old.php?id=1 http://www.mysite.com/new.php?id=1
redirect 301 /old/old.php?id=2 http://www.mysite.com/new.php?id=2
redirect 301 /old/old.php?id=3 http://www.mysite.com/new.php?id=3

and it worked correctly for the base url only (1st redirect)

Now I have simply removed anything after the first line - and it workes fine for all the dynamic urls based on www.mysite.com/new.php

It really troubled me I should admit. Quite a bit of work has been done to achieve our current positions in SERPs and I didn't want to roll back to the old design/structure either.

The other possible question out of this is how to make a rewrite rules with mod_rewrite for the new urls having redirects from the old (non-exsisting) ones. Or in other words:
Task #1 to redirect http requests from the old urls to new ones (accomplished)
Task #2 to make new urls SE friendly (give them a static look)
Would it be ok just to add rewrite rules after 301 redirect rules into the same .htaccess file?