Our postal service is like that as well, I've had boxes just left on my front step that are supposed to be signed for. I've had those second notices about a package pickup when there was no first notice to start with. I had my passport returned to the Passport office and had them call me and verify my address there was never any notice left about that envelope.
It's good to hear that Keepsake was willing to ship it back out at no charge, I went to they're store last summer and found everyone to be very helpful.