i feel that deeds should always provide loot 1 difficulty above the one of the deed, as they become obsolete very quickly as by the time you beat them your gear is much higher than the reward.
EG:
before: recruit mission, recruit reward
after: recruit mission, veteran reward.
I honestly feel that the rewards are bullshit. Maybe the deeds are simply intended to have a challenge and not meant to give a powerful reward.
They could give a cool skin for a deed, for example, but that may divide the community 
agree, that s why i didnt care so far from the deed bug not givin reward.
but the reward should be rewarding.
Maximum power would be a very poor solution.
More chests and more higher rarity chests would make much more sense.
Depends on the deed, really. But when you have a “Back to Basics” deed (play without traits or talents, with 5 power items, on veteran), that could have certainly given at least a commoners chest or something, because it is certainly harder than Champion.
IF they grant rewards, it should be good ones. Well, befitting the challenge.
Before release i thought that in the deeds we would have the opportunity to get cosmetic items.
But there are just the some boring boxes and honestly its efficient to just do quick play.
Having something like cosmetic chests for the deeds would give a special incentive to do this very difficult missions.
Especially seeing that cosmetics seem to be VERY rare.