Issue
Customers may report that address validation stops working suddenly. Typically this is caused by the customer exceeding their monthly count, especially if it is towards the latter half of the month.
If you run address validation in samples, it will provide you with a coded error message. In cases of them meeting their monthly count limit, you should see the following error:
Resolution
Increase or add unlimited address validations under Setup-->Application Settings--> Address Validation. For unlimited address validations, set the monthly limit to 0.
BEFORE you set them to UNLIMITED, you will need to get permission from their Account Manager - Address Validation is billable and has a monthly limit they must stay under.