AA, like most operating businesses, buys databases for regions/countries which verify addresses. When new addresses are created, there is a lag time. It can be as much as a couple of years depending on region.

But, as with any of the silly details of dealing with vendors, just pick up the phone rather than sweating it.