The IMAP protocol can support millions of messages in a single folder. I know of servers that can, too.
It sounds like the client app is doing hashing of the IDs, and beyond a certain point, they are colliding in the hashmap. :-( It probably doesn't even know.
I've got my Asus Eepad's IMAP client talking to my local server and it hasn't done anything funky, but then I haven't ever told it to get all messages in my inbox. Which has a few thousand.
Wade.