It's a miracle

It's not a miracle, just routine business. Banks and insurance agencies are like the CIA of our money, and credit/loan companies have no trouble accessing your information. I briefly worked for a collection agency and it was pretty easy finding out the history of loans or outstanding debt for an individual - you can subscribe to a service that does it for you. They might not have travelled down your credit history long enough to find out you paid the mortgage, they just found a record of your original lending bank with your name and address.