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.
Getting that first E-mail is not too bad; having to sign in to a service I never signed up for in order to stop the e-mail is the pain-point.
I wish more companies would require e-mail verification before activating accounts and sending out a flood of messages. It would also protect their customers, because it is quite easy to request a password reset and then, say, go dick with someone's data-populated chat-app settings.