Thank you so much for the patience. And you know what's funny? If I mousehover on my links (FF, v9) I see four different links! God, it seems a complicated problem... And I don't get the last question: my website is in UTF-8 encoding. Or you mean the target website?
And are you saying that even if I change the encoding of the required URL on the fly it will still be reconverted on their website?