I've thought about this before. I move fairly often. But why in the world should I have to update my address with 27 different places every time. Why can't I simply have a virtual mailing address that I give out to people, and when people mail things there, it gets looked up after it reaches the post office. And then, when I move I simply update the physical address in one spot. I do this already when I set a forwarding address with the USPS.
In order to increase adoption, I was thinking that in addition to a simple domain name, it would also have a human-readable addr1/addr2/city/state/zip format to be backward compatible with current mailing address forms. If you're concerned about redundancy, it can go in here. If the address still can't be read by the post office, it will return to sender or route the same way a dead letter would.
I even thought about making a startup out of this by implementing this routing myself using the post office as a service. In other words, people could register a virtual address with my company, and when giving out their address, give out my company's address where the address-line-2 indicates their "domain". When my company receives the mail, it does a lookup on the virtual address and remails the letter/package to the physical address registered. Since this is a convenience for the owner of the virtual address, they can pay my company per thing routed, so they only ever pay when it actually gets used. But this easily allows my company to pass the remailing postal charge on to my customers. I think remailing would be acceptable to me as a user, b/c 95% of all the mail I get, it wouldn't matter if it took twice as long to get to me. For things that required speed of delivery, I would probably make sure something special happened anyway, like priority mail or fedex. Of course, people are then going to want to do things like get an email about something they received before paying for the routing, which I think would be cool as a user anyway.
Using DNS for routing is a good idea though. It's already redundant and reliable. It also avoids concerns of criminals using this as a way to hide their address, since anyone can just do a WHOIS on it.
I didn't pursue this idea because I figured reading hand-written addresses was a hard problem, and it would make more sense to simply be implemented by the postal service itself to avoid remailing. But how in the world do we convince the postal service to add this feature?