Mail ‘addressed’ to a person or business, not a physical address. The intended receiver is not a building, but a person or entity of some sort at that building. Each person and business would probably be assigned an id number and that is what is written on the address field of envelopes. The post office keeps track of the physical address associated with each person or business, and sends letters to that person or business at the currently specified address. When someone moves, they inform the post office, and all mail is automatically sent to the new address, without need to inform the sender. With a computer database, the system would be easy to implement and utilize with database of addresses that probably already exists. Changes to addresses associated with people would be quick and simple, and could perhaps even be done for the short term, such as while on a vacation. Of course, the current address method would need to be supported for a long time to come; it would take years for people to learn the ids of everyone, especially those they infrequently communicate with. One problem would be sending to families, though perhaps a method could be set up to designate a letter sent to a person to be meant for the whole family, such as ‘family of’ written before the number or something.
This same database could perhaps be extended to include phone numbers. Just dial some prefix (so as to allow phone dialing as normal to work) and then the persons id number and it will call their current phone. Phone numbers are already becoming crazy with cell phones, people with home and work numbers, all that stuff. This could of course create problems with which number to route through to get to the person. Perhaps each person could list multiple numbers for different locations they might be. The caller would be presented a list of these with the number to press for each (you are calling Josie Haberdash. Press 1 to call her home phone, press 2 to call her work phone). Of course, this would create privacy problems: giving out your work number would also mean giving out your home number. Perhaps the list could, if the person desired, give out only certain options, and others would require a certain, perhaps 4 digit pin or something, to be dialed in. That sounds a little too complicated though and few people would be able to remember a bunch of peoples numbers plus their pin.
Even email might benefit from this. The .name domain already has something like this, but it is not widely used, only allows for one person with each name in the world, and is a pay for service instead of a government managed system.