I cannot be sure that what I suggest will work, because this situation with your gateway looks quite pathological to me.
However, I strongly suspect that you simply have to percent-encode all characters beyond ASCII with and pass all characters with ASCII subset (up to code point 127) as is. Just look and compare:
Just for a record: even if you quite redundantly percent-encode each character in the URI, it will work; the only problem is its readability for a user.
And the escaping should be done using this schema: http://en.wikipedia.org/wiki/URL_encoding
In addition to the characters shown in tables, percent-encode all characters with code points above 127.
Just give it a try.