それを見てください:
import urllib
print urllib.urlencode(dict(bla='Ã'))
出力は
bla=%C3%BC
必要なのは単純です。utf-8ではなくasciiで出力する必要があるため、次の出力が必要です。
bla=%C3
私が試してみると:
urllib.urlencode(dict(bla='Ã'.decode('iso-8859-1')))
動作しません(私のPythonファイルはすべてutf-8でエンコードされています):
'ascii' codec can't encode characters in position 0-1: ordinal not in range(128)
本番環境では、入力はユニコード化されています。