The fix:
Export your contacts to a new .pst file. Delete all your contacts. Import contacts from the created .pst file. Fixed