Hmmmmmm. Well, I think I know what's happening, but I don't know *why* it's happening. (It sounds like it is trying to retrieve message headers for a message that no longer exists... but where it's coming up with a nonexistent message ID is a really good question.)
Does your mail server support IMAP? POP3, as the older and less reliable mail protocol, can cause problems in some configurations. I'm curious if this error would happen on IMAP, too -- maybe you can switch to that and try it?
Come to think of it, what mail host / mail server software are you using? I wonder if it's providing the message UUID in a different format or something.
As far as your system logs are concerned, probably won't be anything useful in there, but what I can do is add a check in the code to catch that error and spit out some more information about it. Are you comfortable installing a beta version of the plugin from a tarfile?
[edited: repeating myself]