I'm not sure how your proposal would work in any case. If a database record with your name in it exists (because you bought a house, have a telephone number, got married, got arrested, etc.) looking up any permutation of that data is just a search. I don't know how you make that illegal.
It's true that some laws/decisions about what constitutes public data arguably made more sense when finding that data required making the effort to physically look through the physical files of some town clerk who was probably out for lunch. However, this has been a topic of discussion since companies started selling databases on CD-ROMs and nothing much has changed. So I'm inclined to think that genie is well out of that particular bottle.