By URL you mean your URL correct? Not evaluating an external one?
According to the API, both REQUEST and GET are automatically decoded when interpreting the querystring. It also indicates manually decoding the already decoded data is dangerous:
http://php.ca/manual/en/function.urldecode.php
When you are creating the querystring to pass, you must encode this yourself.
When you type in the actual %XX strings into a urldecode, which one provides the proper results the first or the second? I would assume the first which would indicate that the actual typing into the url is your bottleneck, and not the processing itself (perhaps the browser isn't interpreting the characterset properly).
I can't view either of these ones and I'm not installing new language sets just to check. PHP has always been a pain with multibyte charsets too, hopefully the native utf8 in PHP6 will help this.