Oh no it can def. be from a breach or a prior phishing attack that was successful. Public records would be pretty low on my list on how they got a legal name in this day and age. Credit card attacks, e-mail breaches from the past (there's a website I forget where you can check if your e-mail address itself has been comprised in a data breach at some point), etc. You have to have information to start with to even look for a public record and electronically speaking it's just easier to get the information by phishing or a breach.