If you have the phone at hand, call an Automated Number Announcement Circuit (ANAC). 1-800-444-4444 is one that has been used for years, at least within North America. As for a 'database' of cell phone names/numbers, you can do a reverse look up on a cellular phone if you know how to social engineer techs/CSRs/crappy point-of-salesmen, otherwise, there are several websites on phonelosers.org advertising reverse cellular look-ups, but you gotta pay for them. Making your phone number 'private' means nothing, don't worry about it, if someone wants it bad enough they can get it.
Also your story is totally dubious, try being honest next time.