If these strings are not interned, then perhaps they should be.
There is a similar optimization proposal (w/ patch) for attribute names: http://bugs.python.org/issue5084
If I understand correctly, that would help with unpickling, but wouldn't solve Michael's problem as, without memo, each pickle would still need to store a copy.