You need blocking!
Fundamentally this is an entity resolution problem. An LLM can score pairwise really well but scoring all the pairs would be insanely computationally difficult.
If you can constrain the set of potential matches up front by querying the dataset for things that could be matches it gets a lot more tractable to use an LLM for this.
Are there any heuristics you can use to reduce the search space? You mentioned soundex transformation and maybe prefixes of last names could work? Even if you get the number of potential matches down by a few orders of magnitude this gets more reasonable!
Check out https://moj-analytical-services.github.io/splink/index.html
The coding agent was pretty good at coming up with heuristics for matching - even more than the dozen I suggested from domain experience. And it used some of them sensibly for blocking, too. I'm sure I could get it to perform a little better and a lot faster with more agent wrangling. I did consider using the heuristics just for blocking, and letting a local LLM do the actual evaluation, but if Jev or Jev-like models work as advertised, maybe we can have the best of both worlds.
Thanks for the link, it is an interesting topic.