Some phone lookup services work pretty much well. The most evident application and service is
Truecaller
Just like Whatsapp and Facebook, Truecaller was part of the internet revolution. Some people say it is the largest mobile phone community for mobiles. Truecaller can:
find contact details globally given name or telephone number
When a user registers for Truecaller, names and numbers from their contact list are uploaded to the service's servers for other users to look up. If you've given your phone number to a friend of yours, who saved your phone number in their contact list, and who downloaded the application; truecaller will automatically get your number. As more users register, truecaller indexes more numbers and names in their database.
As of April 2016, Truecaller's official website reports to have 2 billion numbers in its index, a screenshot from my phone:

Do phone lookup services like Truecaller work?
While Truecaller has always worked for me (anectodal evidence), I have to list public reports (which might be considered as evidence) which show that Truecaller works:
Techverse.net has reported
Using it is very simple, just install the Truecaller app on your phone from the links provided at the bottom of this page and as long as your phone is connected to an internet connection, Truecaller will be able to accurately identify any unknown number and provide you details such as the owners name and the place where the number is registered.
bgr.in has reported:
In essence with the Auto Search, users will now be able to get information on a number mentioned anywhere like a website, email or text message. All a user has to do is select the phone number, and hit “Copy,” and Truecaller will pop up the contact information related to it.
thehindu.com has reported also:
Mrinal M., a young entrepreneur and a photography enthusiast, swears by the Nokia Creative Studio application in his Nokia Lumia 525 because the software makes even photos taken using low-end mobile phone cameras look amazing with a unique set of filters.
”Another application which comes in handy is Truecaller – which helps track calls from unknown numbers. Being a food-delivery entrepreneur, I handle a large number of calls each day, mostly from people who call me for enquiries. Truecaller identifies these callers for me.” he says.
PROF. Review reported in a book published on Google Books:
Truecaller is replacing the phonebook to make it more intelligent and useful. It lets you search beyond your existing contact list, identify unknown incoming calls, block calls you don't want to receive, and make personal contact suggestions based on time and place – so you never have to leave the service to find the right contact.
mobileentertainmentforum.org reported:
After installing TrueCaller on an Android, Symbian, iPhone, or Windows phone, a main screen will pop up showing the three main options: call filter, search, and update phone book. The search function lets users search for public numbers, which can be saved to the phone book instantly. Call filter also has a database of phone numbers which have previously been tagged as spam by other users and will notify you when a blocked number is attempting to access the phone. Of course, a user can always put any number they want into the call filter data bank and avoid talking to individuals to whom they do not wish to speak.
In early 2014, Truecaller received a $18.8 million investment led by Sequoia Capital. In October of the same year, they received $60 million from Niklas Zennstrom's Atomico investment firm and from Kleiner Perkins Caufield & Byers. This gives a possible indication also that the service works.