Modifying this portion to something more like this:
.*[^    <>@]+(_at_)[^    <>@]+.*
would allow for this sort of thing, but at the same time make sure that the
messageid contains an '@' and a non-badchar immediatley to either side of
it -- without reguard for whatever else might be there.
No, this doens't bring it up to snuff with RFC parsing, but it would
probably fix your current problem.
I use this for RFC compliance:
   :0:
   * !^Message-Id:[\t ]+<("[^"]+"|[^ <>@]+)@[^<>]*>$
   /scratch/spam
Surprisingly enough, I catch a lot of valid email with it.  Seems that
intel.com, cat.com, attmail.com, excite.com, and others all have non-RFC
compliant Message-ID headers.  I send them mail when I come across
it, and some sites have actually made steps to correct the problem...
So, the lesson to be learned here is that there is almost no 100% 
surefire way to filter spam, and ALWAYS KEEP A BACKUP OF THE MAIL.
But we all knew that already.
Chris