It could be somehow related to the size of the Gmail message ID numbers. I took a look at the headers of some of my Gmail messages; here's the "Message-ID" field from an email sent yesterday:

Message-ID: <51AE1BD8.4050905@gmail.com>

And, here's one from a message sent back in 2008:

Message-ID: <48CE8D81.50506@gmail.com>

The portion after the dot has grown significantly. Perhaps some Gmail accounts have even larger ID values, and are overrunning some string size limit in modest; or, perhaps some versions of modest can't handle the larger string size?

EDIT: I'm probably barking up the wrong tree here, the message ID in Marmistrz' example is:

Which, of course, isn't even a Gmail ID to begin with...