A variant I've often wanted is to make str() return the "clean" type only (e.g. 'int') while leaving repr() alone -- this would address most problems Steven brought up.
On further thought, I'm not sure backward compatibility can be dismissed. Surely code shouldn't care about the str of a callable, right? But yeah, sometimes it might care, if it's, say, a reflective framework for bridging or debugging or similar.
I once wrote a library that exposed Python objects over AppleEvents. I needed to know all the bound methods of the object. For pure-Python objects, this is easy, but for builtin/extension objects, the bound methods constructed from both slot-wrapper and method-descriptor are of type method-wrapper. (The bug turned up when an obscure corner of our code that tried lxml, cElementTree, then ElementTree was run on a 2.x system without lxml installed, something we'd left out of the test matrix for that module.)
When you print out the method, it's obvious what type it is. But how do you deal with it programmatically? Despite what the docs say, method-descriptor does not return true for either isbuiltin or isroutine. In fact, nothing in inspect is much help. And the type isn't in types. Printing out the method, it's dead obvious what it is.
As it turned out, callable(x) and (hasattr(x, 'im_self') or hasattr(x, '__self__')) was good enough for my particular use case, at least in all Python interpreters/versions we supported (it even works in PyPy with CPyExt extension types and an early version of NumPyPy). But what would a good general solution be?
I think dynamically constructing the type from int().__add__ and then verifying that all extension types in all interpreters and versions I care about pass isinstance(that) unless they look like pure-Python bound methods might be the best way. And even if I did resort to using the string representation, I'd probably use the repr rather than the str, and I'd probably look at type(x) rather than x itself. But still, I can imagine someone deciding "whatever I do is going to be hacky, because there's no non-hacky way to get this information, so I might as well go with the simplest hack that's worked on every CPython and PyPy version from 2.2 to today" and use "... or str(x).startswith('<method-wrapper')".