redirecting to new domain, is this possible?

OK, I currently have our main store running on a new webhost on a new domain but realised that there are lots of web pages
with links relevant to the store when it was on the old domain and I'd like to not lose whatever benefit those may bring.

What I want to do is be able to redirect from any old links to the new store.

I have a basic page to redirect the main store page, so for example any previous links to www.olddomain/zen/ will get redirected
to www.newdomain/zen.

However, this will not work with links that go directly to a product.

So URL's like; http://www.olddomain/zen/index.php?main_page=product_info&cPath=1&products_id=156 will now return an error
page.

So is there a script that will, for example, do a search and replace, swapping the old domain fo the new one? Or some other type of redirect script
that would solve this issue? It could even be a situation where it ignores everything after the /zen/ so that it redirects to the main page
of the current store. I just don't want to lose all those old links in our various web copy.

and BTW - I do not want to move the old domain because there are other things on there that I don't want
on the same server as the new (current) store.

(The reason for the move was that we recently had a server crash which forced us to open a new more robust hosting account and in the interest of
speed I set up a clone of our store under a different domain as this was the easiest option for a number of reason I won't
bore you with here. )

And you have no control over nameservers or the ability to park a domain?

OK, the solution is very simple.

Since the new store is a clone of the old store, all folders, files and product IDs are the same, only the domain changed.

So I discovered that cpanel's redirect has a 'wildcard' function that puts any filenames from the old URL into the same folder on the new URL
and it seems to work perfectly. Problem solved (and without even having to look at a line of code :)