This happens to me about twice a year (not a firstname.lastname, but a commonword.commonword. It's like a stupidity-driven dictionary attack). The worst companies I've had to deal with:

Steam - took me multiple emails over the course of weeks, and they actually made me send them screenshots to prove the account was mine. I only went to this much trouble because I have a legit Steam account. Especially funny since I casually told them that I was a hair trigger away from just resetting the idiot's password and hijacking his account.

AT&T - Flat-out refused to unsub me from someone else's phone bills. After several calls to AT&T I finally gave up and called the customer. An AT&T rep actually had the balls to tell me that making me do this was for the customer's protection.