Dealing with duplicate contacts due to linked cards in iOS' Address Book API

Some beta-users of my upcoming app are reporting that the list of contacts contain a lot of duplicate records. I'm using the result from ABAddressBookCopyArrayOfAllPeople as the data source for my customized table view of contacts, and it baffles me that the results are different from the iPhone's 'Contacts' app.

When looking more closely at the Contacts app, it seems that the duplicates originate from entries with "Linked Cards". The screenshots below have been obfuscated a bit, but as you see in my app on the far right, "Celine" shows up twice, while in the Contacts app on the left there's only one "Celine". If you click the row of that single contact, you get a "Unified Info" card with two "Linked Cards" (as shown in the center, I didn't use Celine's contact details because they didn't fit on one screenshot):

The issues around "Linked Cards" have quite a few topics on Apple's forums for end users, but apart from the fact that many point to a 404 support page, I can't realistically go around fixing all of my app's users' address books. I would much rather like to deal with it elegantly and without bothering the user. To make matters worse, it seems I'm not the only one with this issue, since WhatsApp is showing the same list containing duplicate contacts.

Just to be clear about the origins of the duplicate contacts, I'm not storing, caching or otherwise trying to be smart about the array ABAddressBookCopyArrayOfAllPeople returns. So the duplicate records come directly from the API call.

Does anyone know how to deal with or detect these linked cards, preventing duplicate records from showing up? Apple's Contacts app does it, how can the rest of us do so too?

UPDATE: I wrote a library and put it on Cocoapods to solve the issue at hand. See my answer below

The approach that @Daniel Amitay provided contained nuggets of great value, but unfortunately the code is not ready for use. Having a good search on the contacts is crucial to my and many apps, so I spent quite a bit of time getting this right, while on the side also addressing the issue of iOS 5 and 6 compatible address book access (handling user access via blocks). It solves both the many linked cards due to incorrectly synched sources and the cards from the newly added Facebook integration.

The library I wrote uses an in-memory (optionally on-disk) Core Data store to cache the address book record ID's, providing an easy background-threaded search algorithm that returns unified address book cards.

The source is available on a github repository of mine, which is a CocoaPods pod:

pod 'EEEUnifiedAddressBook'