A friend of mine received the letter pictured below (click to enlarge) and asked me about it.
Searching around for American Data Services I found this post on the Snopes forum and this blog post. Basically this is a perfectly legal scam to get 10% of a refund that you may be owed when you refinanced and ended the HUD/FHA insurance from the original mortgage.
The people and companies sending out these letters won’t actually help you get the refund in any significant way but, they will take 10% of the amount up front to tell you to contact HUD. The better thing to do is to check the HUD database yourself and get the refund without paying the fee.
Because it is legal to try to get people to pay for this un-needed tracing service, it has also become the basis of some of the get rich quick scams on the internet. Anyone who does this should be very careful because if you represent yourself as having any affiliation with HUD/FHA you will be prosecuted be the government.
More information is available at About.com here and here, as well as this press release from the FTC.