I had a similar experience after moving once. I'd called the credit card company to update my address and had even received statements at the new address (this was before e-statements were common). When it was time for a replacement card, a year or two after the move, it didn't arrive. So I called them, confirmed my address, etc., they said it had been sent months ago, so they would cancel that card and re-send. So now I can't use my current card even until it expires since the number has been cancelled. Wait a couple weeks, still no new card. Call them again, same deal. Confirm the address, they've sent it, it never arrived.

When the NEXT card didn't arrive I went by my old house and sure enough the folks living there had received all three copies. Then I got to spend a few hours being passed around to various people on the phone with the credit card company before I could find the person who knew about the super secret place where the replacement card address was apparently stored.

Edit: Ha, I just remembered the saga actually continued the next time I moved. Remembering this experience, I wanted to proactively have them change not just the regular address, but also the replacement card address. Unfortunately, try as I might, I couldn't find anyone who would believe me that just updating the regular address on the account wouldn't work. Sure enough though, when it was time for a replacement, it once again went to the old address!