All storing immutable objects in the memo dict does is slow stuff down, due to having a larger hash table, and on some other Python's causing hilarious levels of GC pressure.  Using http://paste.pocoo.org/show/421310/ as a benchmark, CPython get's a 2x speedup on the deepcopy portion, and PyPy a 20x.  Patch is attached.

A slightly cleverer version (or less clever, depending on how you approach the issue) that also works with tuples of immutable content.

Switched to using assertIs, as merwok suggested.

Amaury points out: this is not strictly about immutable objects, but rather objects who's deepcopy is themselves (identity-wise), in some (rare I think) cases this could provide a slowdown.  Specifically a case of [(1, 2, 3)] * 10000 would be slower, because it would review each tuple individually, rather than using the memo'd instance.  I suspect this case is not so common (to have the same identity object, who's deepcopy is itself such as a tuple or object with custom __deepcopy__, many times in a deepcopy object graph), but I have no proof of this.

New changeset e24ad85e9608 by Benjamin Peterson in branch 'default':
don't memoize objects that are their own copies (closes #12422)
http://hg.python.org/cpython/rev/e24ad85e9608