I think the module should be reviewed and made consistent, as Antoine did for nntplib.  I don't know enough about the IMAP protocol to do such a review, or even weigh in meaningfully on the immediate question, nor am I likely to have time to learn enough before 3.2, even assuming we wanted to make such changes at this point in the release cycle.  Putting changes off to 3.3 makes backward compatibility more important, so we may wind up stuck with warts.

Yes a function that returns a datetime would probably make sense.  That would be one way to clear up the warts: introduce a new function and deprecate the old.

A relatively uniformed opinion: it sounds like Internaldate2tuple should take bytes (since it sounds like Internaldate is most likely to be manipulated as a wire-protocol level object), and that Time2Internaldate should correspondingly return bytes(*).  What ParseFlags should return I couldn't guess without learning how the returned result is used in a typical program.

(*) The asymetry in the names of these two functions is already a wart.