One tip I was told at the post office is to make sure to but inside the package a ship to address as well as a return address. They said often if a package is lost and the outside address is no longer legible they open the package to see if there is a clue to where it belongs.
They went on to say that many of the packages that end up in their "lost" bin would be able to be delivered if only a shipping label was on the inside as well as the outside.