ABRecordID's most certainly do change (having learned this the hard way - as a result of multiple machine contact sync)
Matt Gemmell has a nice writeup at iphone-dev-tips-for-synced-contacts
I don't store the composite name, but rather the ABRecordId, first name, last name, an email address and a phone number (the last two of which are used directly by my app).
If I don't get a hit on
ABRecordRef aRef = ABAddressBookGetPersonWithRecordID(addressBook, aRecordId);
I use a bunch of code to find potential matches on last name, first name and then refine it by phone numbers.
As a final aside, I am associating a generated UUID for the contact so that all of this (potentially) fuzzy resolution is abstracted out of the data I'm associating with a contact.