Or do you have one address for UPS deliveries and a different address for FedEx deliveries? (Substitute local carrier names as appropriate.) While that's more work—and pointlessly complex IMHO—you'd just need to set up one ID per carrier and give the correct ID, as opposed to the carrier-specific address.
Anyway, a shortcut to implementing indirection for these less-organized postal services you're describing would be to look up the recipient's ID when the parcel first enters the system and affix a label with the full address. That way the sender doesn't need to know the address and everything else about the delivery can stay the same.
In that scale, nothing is simple, because everything can become expensive on the high run.
Only if you don't consider flexibility part of the task, which is rather short-sighted in today's world. Maybe postal services could afford to be inflexible once, but those days are long past.
In the first place there is not even enough data to know whether the huge investment would be justified.