How do I validate a businesses identity?

You're just going to have to take their word for it, or check manually, because there's no good way to automate this.

Here is a list of every country/state/province's business registry websites, which is the best way to manually verify a company exists:

http://en.wikipedia.org/wiki/List_of_company_registers

I received so much spam after starting my business, I figured there must be some kind of API that spammers are using to get business information, but I've been unable to find such a service. I suspect the information is being scraped from the websites listed in the link above.

Interesting: The USPS has an Address Validation API. Which, admittedly, doesn't really solve your problem either, but might be tangentially helpful.

An additional approach could be to check information against an information provider such as Experian services [1], for instance you could query the credit ranking score and credit summary or something similar.

I have experience with integration with credit card check services and those integrate easily with standard protocols (we used SOAP). Once a customer is connected to our site, we do a background check against Experian database to prevent fraud.

You might contact them for additional information on your specific needs from a business.

[1]Example of Business check, you can freely check if the company is registered http://sbcr.experian.com/main.aspx?link=5502

1. Check the land line telephone number with the provider. Generally land line telephones cannot be transferred easily where as mobile phones can.
2. A private detective agency might be helpful as well but may be a little expensive

Something that we have considered doing is verifying the essential business information, such as address with the state that they are doing business in, and then send them a physical letter with an online verification code.

It takes a small amount of human interaction, and costs about $1 for the letter, but that cost is worth it to us.