So you want your header line to be this, right?
header("Location: http://www.destinationsite.com?param=1¶m2=2¶m3=3");
If you've used str_replace to replace & with %26 you'll need to convert it back using
$url = str_replace("%26", "&", $_GET['url']);
After doing that just echo $url out and see what you get. It should be what's above. If not, let me know what it is.
edit: urlencode() Thanks konsu. That's what I was trying to think of.