In order to retrieve the deleted contacts, you can use the Time Machine. Open the Address Book application, click the menu bar icon and select Enter Time Machine:

Select an older date to find the missing contact, click the contact icon and then press Restore. If this doesn't help, check the official forum for further solutions.