This happened to me a few weeks ago. I live in a relatively new subdivision (only 5 houses on my street), and the AA website wouldn't accept it. I called and an agent was able to override it. No bills or verification required.

It did take two phone calls, but only because the first person keyed in some of my info wrong. Hope that helps.