> Sorry, I don't follow. I realise that the refcounts will be different;
> but pickling an object should surely be independent of the refcount as
> there is no need to include the refcount in the output?

There certainly is a need to consider the refcount. Else the memo
would not work.

> What other way (using pickle or not) can I convert a generic immutable
> Python object to a string to use as a key in external storage?

You will have to come up with your own serialization function. There
are MANY reasons why using a pickle cannot work. For example, in a
dictionary, the order of keys is not guaranteed, and might change even
though the dictionaries compare equal.

> Currently the documentation points out that the output may be different
> between pickle and cPickle which implies that the output will be
> consistent for a single module.

I doesn't imply this at all. The sentence says just what it says: don't
be surprised if you pickle the same object with pickle and cPickle,
and get different results.

> If pickle is not required to produce consistent output for the same
> input (and refcount isn't really part of the input in this case; it is 
> a side issue) than can this be documented?

It's certainly possible to document that, yes. Can you propose a
specific patch to the documentation?