I fixed this while working on PEP 3154 [http://hg.python.org/features/pep-3154-alexandre/rev/eed9142d664f]. The relevant piece is

@@ -420,7 +424,13 @@ class _Pickler:
             write(REDUCE)
 
         if obj is not None:
-            self.memoize(obj)
+            # If the object is already in the memo, this means it is
+            # recursive. In this case, throw away everything we put on the
+            # stack, and fetch the object back from the memo.
+            if id(obj) in self.memo:
+                write(POP + self.get(self.memo[id(obj)][0]))
+            else:
+                self.memoize(obj)
 
         # More new special cases (that work with older protocols as
         # well): when __reduce__ returns a tuple with 4 or 5 items,

It would be pretty easy to backport this to 2.7 and 3.3. It is also good to mention that that only protocol 0 and 1 are affected.