Sorry for the delay with my update. I trawled google for answers and the 2 most popular were;
1. do a repair
2. check for duplicated contacts - as suggested here.
I did the repair, then asked my MD to check his groups for duplicated contacts, suggesting if he had duplicated names with different email addresses suffix the names 1, 2, etc. He later told me that everything now appears to be working. I still don't know if he had any duplicates, he fends that question away, so I can only presume he did have.
Thanks for all the help.