Я думаю, что проблема в том, что вы сначала urlencode последней части URL, который затем включаете в другой URL.
попробуйте использовать urllib
для этого:
import urllib
urllib.quote("http://mydomain.com/#url=http://stackoverflow.com")
или когда вам нужно что-то цитировать:
urllib.unquote("http%3A//mydomain.com/%23url%3Dhttp%3A//stackoverflow.com")
С уважением