There are all kinds of ways to find people, it's pretty much impossible to stay under the radar with taxes, bill, work records, bank and other accounts etc...
Marriage is a public record and not too hard to trace and companies who track debtors down have access to far more comprehensive databases and other resources than the ordinary person on the street.
It's possible they have taken action against you in some form but you are unaware as you have not kept them updated on where you are and there are procedures in place so that not knowing where someone is doesn't not prevent debtors from taking action.
Which country has your former husband gone back to?
Do you or he own any other property or assets?
Have you ever checked your credit rating or had any problem getting credit like credit cards, store cards, car finance, mortgage etc...?