alt Hacker NewsAnother tidbit, based upon finding out which company the phone number belonged to: you could go to the library and access business directories. Think the yellow pages, only they were geared towards businesses rather than towards consumers. Print versions were broken down by industry, but electronic ones (on CD-ROM) were searchable. It was also a tool for looking for unadvertised jobs, since those directories seemed to be geared towards making cold calls (albeit, for people doing sales).
Replies
I worked on a project in 1990/1991 (pre-WWW) that involved making the phone book electronically accessible. For development my client purchased CD-ROMs containing the White Pages from the entire NYC tri-state area (NY, NJ, and CT), making it trivial for me to search by name and/or number. Once the web had been around for a few years, reverse-lookup became commonplace.
In 2000 you could go to the library and look up the number in the Polk directory. There was one for each borough. There was an alphabetical section, a section by street address, and a section by phone number. You can still go down to the library and use them, for example if you want to know what was at 867 Madison Ave in 1926, or who had the phone number PENnsylvania 5000.