And which access method do you use?
I'm using Exchange 2010, and have had problems getting IMAP to work, though POP3 worked.
I've also used a Gmail mailbox with both POP3 and IMAP.
I know of a successfully installed Linux mail server of some sort (i'm not very knowledgeable of Linux-y things) with IMAP
I'm wondering,specifically, if older versions of Exchange support IMAP...