I don't follow when you say that there is no way to URI encode a non ascii character. 
Ie : España -> Espa%C3%B1a where ñ is encoded using two bytes C3 and B1. 
This would be utf-8 uri encoding

What is happening (I just realized) right now with my implementation is 
that it is not encoding stuff into UTF-8. Ie:

España -> Espa%F1a 

This is actually a form of ISO-8859-X and I am not sure why this is happening.

If I do not use the Utf8String class as you suggested I get :

España -> Espa%FFFFFFC3%FFFFFFB1a 

which is almost the UTF-8 encoding if it wheren't for the FFFFFF. So I guess what you suggest would work if you are know beforehand that you  will get the extra FFFFFF  

I am no 'wierd-char' expert so .... thoughts ?