It's been a while since the flurry of de-anonymizing data papers back in 07-08, but my takeaway impression was that you can't truly de-anonymize large datasets without destroying its utility.
See this: http://godplaysdice.blogspot.com/2009/12/uniquely-identifyin...
I imagine gender and DoB factor in heavily to something like a recommendation engine, and I'm sure zip code would come into play when trying to get those last couple percent as is the case with the Netflix prizes.