Well, you've said a mouthful but no useful information (for creating a pattern from old to new).
Let me first recommend a thorough reading of the mod_rewrite tutorial linked in my signature (including the coding examples).
THEN I suggest that you consider your site redesign so that the old pages can be redirected via some pattern matching to the new pages. If you do that properly, I'd suggest that my_query_string is the filename of the new script, my-new-page.php so that you can actually use mod_rewrite to redirect to the value of my_query_string [R=301] THEN on to my_query_string.php without displaying the .php file extension. Some call it "pretty URIs," I call it extensionless URIs. If my_query_string.php actually gets redirected to a file handler to access the database (e.g., for the title field rather than the id field), that becomes rather trivial, too (e.g., http://wilderness-wally.com).
Okay, perhaps I've raced too far ahead of you. Look FIRST and FOREMOST to creating a pattern between my_query_string and my_new_page as the babystep before running as I was describing.