I legally changed my name over a year ago, and I still get calls from recruiters once a week or so asking for my old name.
Why? Because they have an old copy of my resume from before my name change. This also leads to me explaining that I don't work at my previous employer anymore and that I've found a new job that I love. They just don't give a shit about having up-to-date records.
My entire name was changed: first, middle, and last, and my new name doesn't resemble my old one in the slightest. It's very awkward having to explain to them that the name they asked for isn't my legal name anymore (and I'm half-tempted to be glib and say "he's dead", but I won't because that could get me in big trouble if they believe it and it gets back to the authorities that I've been using my name change to fake my death).
It's especially awkward, because it forces me to out myself to them as transgender, since my old name was unmistakeably male, and my new name is unmistakeably female. Hell, I'm very much out and proud, but it's just plain awkward to have to tell a recruiter over the phone when they're not expecting it and when it's my very first communication with them.