I had a similar experience- moved to an area with a new ZIP code (<2 years old) and while most services were fine, Google Address Verification didn't know it existed. I couldn't use my credit card anywhere that used Google to see if the address was real. Multiple customer service reps said there was nothing they could do; my address was just not valid for their system. I imagine it eventually made it in to Google's vault of 'knowledge,' but by that time I had moved away to a place Google thought acknowledged the existence of.
