I think the only way you can provide this service by getting other people to trust you on it is to use an established escrow from the forum.

So if you want to recover a person's wallet and you can see let's say 1 btc in his address, you provide the exact same amount to the escrow so the client feels safe that even if his wallet gets compromised, he can claim back the funds from the escrow. And when you recover the wallet, you hand it over to the escrow, and they give you back your funds + 5% or whatever your charge is and hands back the account to the account owner.

Maybe that way people can trust you since it's really hard to trust strangers on the internet.