Thanks for pointing out the make_header(decode_header(...)) idiom, which I was indeed not aware of.  It solves the problem perfectly.

I agree that it is a doc bug.  While make_header is documented on the same place as decode_header and Header itself, it is not explained *why* I should call it if I already have in hand a perfectly valid Header instance.  Specifically, it is not at all clear that while unicode(h) and unicode(make_header(decode_header(h)) will return different things -- I would have expected make_header(decode_header(h)) to return an object indistinguishable from h.

Also, the policy=default parameter in Python 3 sounds great, it's exactly what one would expect.