HERE is a link to the FAA operating certificate search page. If you know what the name of the business listed on the certificate is or the type of certificate (pt.135 etc..) and the state it is located in, this search function will display all company certificates and list the address and aircraft types if you click the company name on the state list. I doubt that a company will be listed here until after the certificate is in force.
Good luck
Best regards,
Westhawk