I would not trust any wallet that pays transaction fees in your place... It would mean they'd lose money each time you created a transaction, which would basically mean they'd have to have some other kind of revenue originating from you... This would probably mean they'd (selectively) scam or bombard you with ads/sell your info.
I wouldn't trust a web wallet, exchange wallet or casino wallet anyways, but one that would brand itself completely free would raise an extra suspicion....