I had a very similar situation when I moved not too long ago.

I couldn't arrange for gas service before I moved into my home because the gas company's web site would only accept Google-blessed addresses.

I had to actually move in, and then go down to the gas company office with a copy of my lease to prove the address exists.

Strange, since at some time in the past the gas company payed many thousands of dollars to run gas service down my street. But, like in most big organizations, I suspect the web people and the company data people don't talk to one another.