In the mid-90s, at the very starting edge of the dotcom boom, I was the lead tech guy behind a project, we put a nationwide yellow pages database on the web, ypol.com.
At the time, nobody else had done it, but we were sure that many other people had had the same idea. And since it's rare for someone to care about finding a plumber or locksmith in another state in the middle of the night, of course I had location based searches from the start.
It was, in fact, my first real encounter with using Oracle, Sybase, and using Perl to interface to a DB. (This was before Perl5, so there was no DBI module, so it was all oraperl.)
It looks like someone has actually patented the idea of location based searches on a online yellow pages database, has put together an investor-based lawsuit machine, and has fired the first salvo by suing Verizon.
I'm pretty damn sure my old YPOL project is prior art. I'm even willing to testify on that point...