I wish I could contribute towards a solution, but i can't.
I am just registering my interest here as there are at least two cases of this occuring on our system too.

One machine has the service pack 1 installed, the other doesn't.

As with the other cases posted so far (is this correct or have i assumed incorrectly?), our IMAP server is not an MS Exchange Server.