Interesting question. I don't see any real viable alternative to manually copying the collection since CopyTo will only allow you to get the values (and not the keys).
I think HollyStyles' Hack would work (although I would be nervous about putting a Replace in a QueryString - obv. dependant on use case), but there is one thing thats bothering me..
If the target page is not reading it, why do you need to remove it from the QueryString?
It will just be ignored?
Failing that, I think you would just need to bite the bullet and create a util method to alter the collection for you.
UPDATE - Following Response from OP
Ahhhh! I see now, yes, I have had similar problems with SiteMap performing full comparison of the string.
Since changing the other source code (i.e. the search) is out of the question, I would probably say it may be best to do a Replace on the string. Although to be fair, if you often encounter code similar to this, it would equally be just as quick to set up a utility function to clone the collection, taking an array of values to filter from it.
This way you would never have to worry about such issues again :)