Hi All.
I am experiencing the same problem with an exchange mailbox here in our department.
It is only happening to one persons account - across three different computers (Macmini, MacBook Pro, iMac - all running 10.6.2)
The strange thing is, my personal exchange account works fine and does not have this issue when I set up my account on these machines, it only affects the particular user. In alot of these threads I have seen suggestions about rebuilding the mailbox and repairing file permissions etc. These all apear to be focusing on the issue being a local client side problem, but my experience is the contrary. However, I have been working with the exchange system admin, and the mailbox itself has been checked for consistency, and even moved between storage clusters to eliminate a network issue. However, the mailbox itself works fine when set up in Outlook 2007 on a windows box, and even behaves reasonably well in entourage. There is something with Mail (4.2) and exchange (2007) that is not behaving itself, but only seems to affect particular exchange accounts.
His mailbox is about 1.1GB which is by no means too big for exchange to handle, and none of his folders have more than 5000 items (the recommended limit for exchange 2007).
Just thought I'd throw this into the mix to help narrow down potential causes.