Apple Mail only synchronizes Inbox with Exchange 2007 to a specific date

Have a very strange issue going on with Apple Mail and Microsoft Exchange.

Our office is predominantly PC based, using Exchange 2007 as our mail server. Recently, we started to purchase MacBooks for our users. For the first two users, the built-in Apple Mail application worked flawlessly to setup and synchronize mail accounts of several GB with no issues. Then, when setting up a subsequent MacBook we found that the Mail application stopped loading the Inbox at a very specific date. No matter what it would not load mail in the Inbox past that date. Strangley the other folders of the profile all load and synchronize fine (Sent items, Deleted, Drafts). Many solutions were tried, including:

1. Rebuilding the mailbox

2. Synchronizing the mailbox

3. Manually deleting the profile in Mail, rebooting, and making a new profile.

4. Manually deleting the profile folders from the directory structure, then making a new profile.

5. Archiving the users mailbox so the size is managable (a few months of Inbox and Sent Items)

6. Making sure all mail was marked as read.

Eventually we gave up. Since then we have setup a few more MacBooks and there were no Mail issues....until last week when upon setting up a new MacBook we came across this very same issue with a different user. We tried all the tricks listed above and still the issue persists.

Exchange is up-to-date as is Apple Mail.

This is very frustrating. Any suggestions?