I just wonder if all private land in the US traces its origin to a patent, or if the patents were established on property people already owned on the frontier as the governed area expanded, so the government could say they granted it. I don't think there was any mass eviction once local governments were established so I'm inclined to think the latter.
Not all land rights originate from patents from the U.S. Government.
A famous example, Manhattan was purchased by Dutch colonists from Native Americans in 1626. See https://www.u-s-history.com/pages/h2122.html
I would further hazard a guess that most original land records in the first 13 states have very little to do with the federal government. The U.S. Constitution recognized under section 2 the rights of state citizens, including the right to hold and dispose of property, either real or proper. Similarly as new states entered the union (e.g. Texas) the land records of the state would generally be considered to be appropriate and sufficient without any federal action.
All of this makes good sense when you consider that virtually all of the "founding fathers" were in fact land owners before the revolution of 1776.