I agree with you that, they need some sort of legal backing to operate efficiently in a society where everything seems like a scam attempt and their services seem to be a difficult one for this generation because it has to do with accessing someone holdings, regardless of how long the wallet must have stayed and yes I also agree with you that, they need to scrutinize their technicians because the illustration you have earlier is a good one and they also need to be paying their technicians well so as to get them focused on their job.
The recovery of lost wallet is a very difficult job and that is why many of these services do charge huge amounts of money because their job involves patience and timely calculation of the right tools to use to recover lost funds.
I will not blame any of these services when they charge too high from customers since instead of losing the fund, it is better to recover it with a substantial fee or bid.