This error message is referencing the donor's address.  The message does not indicate that the address does not match the billing address of the credit card, but rather that the address format is incorrect. 

Possible causes:

Online Donations (NetCommunity, NetSolutions, eTapestry)

Batch Transactions (The Raiser's Edge) - When a transaction is processed in Batch, The Raiser's Edge automatically includes the preferred address on the Bio 1 tab of the donor's constituent record because there are no address fields in a Gift Batch.  The preferred address does not have to match the billing address for the card, but must be a valid address.