According to rfc 822 a message id must
be enclosed in <> and contain an address,
i.e. some simple words separated with
an @.

I haven't tried it, just looked at the source,
 but 

messageid = "%s.%s.%s%s-%s"%(time.time(),
 random.random(),
 classname, nodeid, 
 self.MAIL_DOMAIN)

in mailgw.py and elsewhere breaks this rule.

Logged In: YES 
user_id=6405

So would making the format be %s.%s.%s%s@%s be OK? If not, 
what's the part after the "@" supposed to be?

Logged In: YES 
user_id=6405

Ah, righto. Yes, the message-id is supposed to be 
<some.string@SHOST> where SHOST is the sender's host. It's 
actually supposed to match the host part of the Sender: 
header, but that's obviously either changed in a later RFC 
or is just ignored (a few sample e-mails I just looked at 
had all sorts of combinations of things.)

Upshot: I'll change it so the format is just 
"<%s.%s.%s%s@%s>" with the current arguments. Note the 
addition of the angle-brackets too...