I think that the tuple is not the problem here, it's the fact that so many objects are recorded in the memo to later rebuild recursive structures.
Now, I believe that recursive structures in pickles are not very common, so the memo is mostly useless in these cases.
Use cPickle, it's much more frugal with the memo, and also has some options to control the memo (read the docs, I forget the details and am in a hurry).
Perhaps pickle could grow an option to assume that a data structure is non-recursive ?! In that case, no data would be written to the memo (or only the id() mapped to 1 to double-check).
The memo is also for sharing. There's no recursion in this example, but the sharing may be important: a = [1,2,3] b = [a,a,a] --Guido van Rossum (home page: http://www.python.org/~guido/)