Actually, it is a problem with Mail. I administer an email server, and only Mail has problems with it. I have the exact same problem as the first poster. If I check with Eudora, or any other client, I NEVER have the problem.
This is definitely a bug that Apple needs to fix. Or at the very least, if they can't fix the bug, don't make Mail stop checking until the error message is addressed. Just let Mail continue on.