homepage

The return type of email.header.decode_header is not consistent. When there are encoded parts the return type is a list of (bytes, charset or None) (Note that the documentation says it is a list of (str, charset)). However, when there are no encoded parts the return type is [(str, None)]. Note that, at the end of the function, there is a routine that converts everything to bytes.
Compare:
In [01]: email.header.decode_header('=?UTF-8?Q?foo?=bar')
Out[01]: [(b'foo', 'utf-8'), (b'bar', None)]
In [02]: email.header.decode_header('foobar')
Out[02]: [('foobar', None)]

Yeah, don't use that, use the new APIs.

And what would the new API be?
There is nothing pointing to it either in the documentation https://docs.python.org/3.4/library/email.header.html or source code.

Right, it's provisional in 3.4. I'm working on the doc rewrite now (although I suppose there's a chance it won't get accepted for 3.5, I expect it to).
Take a look at https://docs.python.org/3/library/email.policy.html. Basically, if you use EmailMessage instead of Message (and therefore policy.default instead of policy.compat32) header parsing and decoding is handled for you.