This was an odd one, I had a new user in the Global Address List (GAL) with no email address.
The account was in use and so I didn’t fancy deleting and recreating it, so instead, ADSIEdit to the rescue.
On the Exchange server, open ADSI EDIT (adseedit.msc), navigate to the user and the field “showInAddressBook” and remote all the entries other then these:
Save and allow it to replicate. Done.