When synching contacts, an error was being logged by the Exchange sync engine stating that an element was failing validation.
The element was as follows:
A value of 'http://' was not valid.
The customer had set a pers_website value of "http://" for a large number of their Person records (possibly by import).
A number of these Person records had been added as user contacts. Since "http://" is not a valid URL, EWS was rejecting the value when the synch was run.
NULLing the invalid pers_website values resolved the issue.