The basic problem here is that the "one obvious way" to some people
(including me and Martin v. Löwis) is to use a dictionary.  Further,
there is the problem of conflating types in a user's mind -- right now,
dictionaries are all about looking up and returning values, while sets
are not.  

The current notion of sets corresponds neatly with what folks learn in
their basic math classes.  In contrast, the notion of "canonical
representatives of an equivalence class" is a more advanced mathematical
concept, one that many people are never taught.  This is even more
problematic in Python because the operation of finding canonical values
is hidden behind well designed __hash__ and __eq__ functions (for
example, it is not at all obvious how Decimal(3.0), float(3.0), and
int(3.0) all have the same hash value).  

An additional problem is the modification of set.add() so that it
violates Python's norm of having mutating methods return None.  We
should keep the language consistent in this regard.

Also, I should comment on the "appreciable memory savings".  This saves
only a single pointer (4 bytes on a 32-bit build) out of three per
string.  But the string object itself takes up memory, so the percent
savings per string is smaller than you would might expect (typically
less than 15%).

Finally, the spirit of the language moratorium is to make it so that
other Python implementations don't have to change for a few years.

FWIW, I am already going to expand the set/frozenset documention to show
some techniques for accessing and using sets.  I can add a link to a
get_equivalent() recipe that makes it possible to retrieve canonical
values from any container including sets.  That recipe uses all the
containers as-is, no patching or API changes needed.