Back up all data.
In Address Book, select File ▹ Export... ▹ Address Book Archive... and save the archive to your Desktop.
If you use iCloud, disable contact synchronization in the iCloud preference pane. When prompted, select Delete From Mac. Re-enable synchronization. Wait for the contacts to re-synchronize, then test.
If you don't use iCloud, or if the contacts fail to synchronize, delete all contacts from Address Book, then select File ▹ Import... and import the archive you created. It may take a few seconds for the contacts to be indexed. Test.
If you don't like the results of this procedure, quit Address Book. In the Finder, select Go ▹ Go to Folder... from the menu bar, copy the text on the line below into the box that opens, and press return:
~/Library/Application Support/AddressBook
Restore the folder that opens from the backup you made before you started.