About a year ago, I did a project for de-duping customer entered contact info. We had less than 100k records for any particular region (Bay Area, New York, etc.) From what I recall, we were able to confirm identity in about 80% of cases using Name, DOB, and zip code.

By far the best metric is phone number, that bumped us up over 97%. If the comparison was limited to only three metrics, then we would use Name, DOB, and phone number. In reality, we also compare zip code, street address, and contacts (like friends on facebook), in that order.

It would be interesting to see if on average, people change their phone number less often than their name (marriage) or address (renters).