OS X Mail.app: Old mail not downloading/showing after reconfiguring exchange account
The 'find the answer to your question 5 minutes after asking it' syndrome strikes again: using the Mailbox menu's Rebuild command fixes the issue. You can select all the folders for which this needs to happen before using the menu item to save yourself some time (but beware that all this syncing might take a long time if you've got a big mailbox).