> Also, isn't day supposed to be space- rather than 0- padded?

This is not clear to me.  RFC2822 (referenced from RFC3501 for internal date) discusses date formats, but as used in the header.  In this case, day is specified as "([FWS] 1*2DIGIT)", which implies optional space and 1 or 2 digit day.  I am not sure this disallows leading-zero format.  But this date spec also says dates should be space-separated (like "12 Jan 2011"), and clearly INTERNALDATE needs "-" (like "12-Jan-2011").  Therefore, I cannot see this date format as being authoritative fro INTERNALDATE.

Also, RFC3501, in chage #71, is extra confusing in that it puts the 3-letter month in all-caps.  Python's Internaldate2tuple(), e.g., cannot handle this currently (nor can it handle a single-digit day with no space or 0, but its regex does handle a leading zero, which led me to think 0 is OK).

Also, it seems that gmail's imap server and Dovecot imap server return leading zero, not leading space, when you fetch INTERNALDATE.  So I concluded from all this that 0 might actually be preferred.  If this is true, leading zero is better also in that it is less error-prone (e.g., strip can remove the leading space, which will cause problems).

I'll keep looking for definitive info, but if you know of some I missed, please let me know.