What kind of law, premise, or arrangements dictate this kind of info
and its publicly accessible nature?
It depends on the jurisdiction.
The general rule is that there are no centralised records. Back in the bad old days in England, if you bought land then you had better have made sure the vendor could give you a full set of deeds showing who sold it to whom all the way back to the Norman Conquest, or you were liable to some smart-alec turning up with better title and kicking you out.
In Australia (and many other places), we have Torrens title, which means that (pretty much) all land is registered with a government agency called something like the 'Land Titles Office' or 'Registrar of Titles'. Torrens title only exists where it is created by legislation. The relevant legislation would specify what records are made public and how.
In Victoria, Australia, the relevant legislation is the Transfer of Land Act 1958 (Vic). Section 27 provides for the contents of the register of titles. Section 114 says that anybody can come in and have a look at the register of titles i.e. see who owns what, and that the Registrar may give someone a certificate reproducing information from those records (for a fee). Section 27C(3) provides for access to historical records (who bought what when, even if they subsequently sold it).
The Victorian Registrar of Titles has kindly put most of this information into a computer database and made it available online (for a fee). For a fee, you can get a bulk download of the entire thing, which a number of companies have done so they can publish the information online, sell it, or combine it with other data. Another example is when you want to build a freeway; you can go to the Registrar of Titles and (for a fee) get a list of all the property owners along your desired route so you can talk to them about selling their land to you (see also 'compulsory acquisition').
Apart from government property records, another important source of information about property dealings is real estate agents. In each State and territory of Australia, real estate agents report sales to their local real estate institutes, who have arrangements with various companies to sell the data. However, this data set does not include proprietor names. Companies will collect data from both real estate institutes and government title registers and publish the combined data set. The legal arrangements around this kind of data include various contracts and the Privacy Act in each State and territory (and the Commonwealth).
I don't know much about US property law but I get the impression from television that all property records are kept in the local courthouse and you can fish around in the filing cabinets if you are sassy to the person at the front counter.
The next question is, as mentioned in other answers, what name the property is registered in. This can be a trustee's name. If the trustee is a company then, depending on the jurisdiction that the company is registered in, there might be a record of its ownership. If someone is motivated by privacy then they will set up a company in a jurisdiction that does not splash their name around e.g. Delaware or the British Virgin Islands.
Then you ask whether you are typing in the address correctly or are you searching an incomplete database. Some systems are picky about how you format the address; perhaps they record the address as Springfield East and you are typing in West Shelbyville. In terms of incompleteness, if the last transaction on a property was 50 or even 30 years ago then in a hypothetical jurisdiction the relevant document might not have been scanned/keyed into the online database.
