The reverse indexes were usually quite expensive. We had them in the lawfirm I worked in years ago. You could get a guy's telephone number, look it up, and then call his neighbors, do whatever.
The difference between this service and Google is simply availablilty. Anyone with access to a computer can find a person now, as long as the number is in the system (Google lets you opt out).
I've yet to see a local library that didn't have one of the criscross directories. Having google provide it makes it slightly easier to obtain.
The thing is, a lot of the information that the government collects and considers public record is not information that it has any business collecting. The same goes for most corporations.