Mail.app on Lion with Exchange doesn't get updates
Solution 1:
Try the rebuild utility through the app, I had a very similar problem and this resolved it for me. Best of luck.
Solution 2:
1) Run the following in Terminal.app:
sqlite3 ~/Library/Mail/V2/MailData/Envelope\ Index vacuum
2) And then select your Inbox, and select Mailbox->rebuild.
Worked for me :)