Are you sure? Does the contact have the First Name and Last Name and Organization fields filled in? In my experience the only time I can find a contact by company name is if First Name and Last Name are blank.
I am trying Power Search as a substitute for Google Search. I find it ironic that I have to replace the search app for a Google product.