I just ran into exactly the same problem and was quite disappointed to see that urlencode does not provide an option to use percent encoding.

My use case: I'm preparing some metadata on the server side that is stored as an url encoded string, the processing is done in python.

The metadata is then deocded by a JavaScript web UI.

So I end up with:
urllib.urlencode({ 'key': 'val with space'}) which produces "key=val+with+space" which of course stays that way after processing it with JavaScript's decodeURI().

So basically I seem to be forced to implement my own urlencode function... Most thing I like about python that it always seems to have exactly what one needs, unfortunately not in this specific case.

IMHO Stephen's suggestion #3 makes a lot of sense, while '+' maybe correct for forms, it's simply not useful for a number of other situations and I was really surprised by the fact that there's no standard function that would url-encode with percentage encoding.