I get the following message when syncing my Blackberry 7750 w/ Outlook XP.
Unable to get an Outlook or MS Exchange record. Lack of network access to MS Exchange Server can cause this problem
This happens when trying to sync the contacts. The error comes up when it is on about number 630 of 980 contacts. I click OK & then it doesn't sync the rest.
I have installed all the patches on Blackberry's website regarding this issue (KB-01172 ) but it still occurs.
You might try exporting your contacts, copying your pst file to create a backup, then delete and import your contacts, that should clear your data corruption.