I've often thought about this. In the US, addresses are traditionally written in the format:

[City], [State] [Zip]

The state (and often even the city; there are free datasets for this though they're not perfectly reliable and more expensive) can be inferred from the zipcode, so it seems logical that we ought to prompt first for the zip and then help users along by filling the state on their behalf. I suspect his is not done because people are so used to the City -> State -> Zip pattern, asking them to fill the zip first just breaks their expected flow; a "surprise" that makes them think.

I used to work on a case management system for legal aid attorneys that did these lookups and we had to explicitly train them to enter the zip code first (changing field order or tab order didn't help) -- otherwise, they'd never have used it; and some of them still refused to use it, but those who did appreciated the time savings.

In the UK, a lot of sites just ask you for your postcode and house number. The postcode allows pretty much everything else to be looked up. I assume there's a fallback to full address in all of these sites, but I've never had to use it. It's a great timesaver.