Hi,
I had the same problem. I received mail for my exhusband and his new partner from various debt agencies looking for them. He had never lived at the house I was in, and I had reverted to my maiden name so was very annoyed to say the least!
I also checked my credit file as we had no remaining debts jointly. However, please make sure, as oneeyedvic suggests, that you contact ALL credit agencies. Its surprising the differences in information each company holds.
I later found out that they had found me via an address he had supplied when applying for credit that we lived together at.
Thats probably badly worded - will try and explain better!
He applied for credit and had to give addresses he had lived at in the last 3 years. One of the addresses he supplied had been our marital home. They got my details from records at that address and then tracked me to my new address.
Apparently it was all from public records/credit files and so they had done nothing illegal.
One of the credit agencies (I'm sure its equifax) show a section on assocaite searches. Even if you have no financial link - have a look in that section. Also I would write to all agencies and make sure there is no mention at all of your ex anywhere on your file. Its a short form you have to fill in and could be well worth it!
Good luck :o)