I suspect that the answer is simple. Have you never noticed that some mail from banks and such carry a little notice in the return address? I forget the exact text, but it basically tells the usps that they do not want their mail forwarded. Instead they want to be notified where you moved.
They probably sent you something, had it bounce and found out your new address. On the other hand, the usps has a
whole raft of ways to keep one's mailing list up-to-date. I would be more surprised if they
didn't know you moved.