Reply to internet address prompts user to setup new contact

I have a couple clients that receive a dialog to setup new contact when responding to an email with external address. This is not a global issue as it does not happen with any other users. Any ideas? Could it be an issue with the Recent Contacts view and the “Do not automatically add contact…” in preferences?