If I were to start a business listing, and I want business owners to be able to signup for the service and edit/update their listing, what's the best way to validate that a person that calls is indeed the owner of the business?
There is no easy way to do this.
You could ask for their company web site address and their email address. If the email address domain does not match the web site, you might have a problem.
US or global? Do you need the actual owner (with the understanding that there may not be a clear majority owner), or just someone who works in the company and has some authority?
I think the method used by Google Apps is the one simplest to automate and scale globally -- require them to make a unique change to their domain's DNS, or upload a file to their website.
Depending on your state, there might be a electronic registry you can purchase a subscription for. I don't know about Texas, but in Denmark the governments "Commerce and Companies Agency" maintains an electronic database of all company registrations which you can subscribe to. Additionally, some providers of yellow pages have enriched versions of the same data available for subscription.
Side note 1: If I was contacted out of the blue, and asked to fax a number of papers to verify ownership, in order to gain access to a webpage... I would almost certainly not agree to that.
Side note 2: Be careful about publicizing information about companies without their consent. See the Get Satisfaction debacle...
Google Maps and other local maps services with business listings just call the phone number provided in the business listing: http://maps.google.com/support/bin/static.py?page=guide.cs&guide=21029&topic=21034
I think Brian is on to a pretty cool idea. If you want to have business owners list their businesses on a website(after you have attracted them to your website), I think using both Keith DeLong's idea and Gary E's idea and combining these two would be great.
And if there were a problem with the email address matching, what you could do is send a confirmation email to that email, and if it's accepted then you can have that email address and the business listed.
You could probably implement Keith's first point after they have signed up and listed themselves that way.