Answer
For successful address matching (called geocoding) with Address Finder Web Service, the address must contain a certain combination of fields.
Possible combinations for successful geocoding at the house level:
houseNumber & street OR P.O. Box
OR
street & intersection
AND
city & state_prov
AND / OR
zone