1: Hero Attacking - If the Hero does not deal sufficient enough damage to deal any hearts to a monster, may they still spend their surge to recover fatigue?

Ran into a scenario where the Disciple was completely fatigued, made a move, made a successful attack which dealt no damage, recovered a fatigue using a surge, and spent the fatigue recovered to; Holy Power -> Prayer of Healing -> Cleansing Touch, removing conditions from themself and an adjacent Hero. Disease on the Disciple - (which afflicted the full fatigue upon the start of that Heroes' turn), and Immobilize on the Berserker - (with the intention of preventing an attack for a full turn)

I've looked around, and there doesn't appear to be any indication that this is or isn't allowed. I think it should follow the same rules as applying conditions, which generally require at least one damage to be dealt.

2: I got a little greasy on the Finale playing the Overlord in the Shadow Ruins Campaign, although I did handicap myself slightly to give the Heroes an advantage. The player controlling both Heroes certainly didn't find me laying 3 traps on a single Search very appealing. (I had actually planned to run back past the doorway, close the door, and lay the traps on the door - but he decided to Search instead of approaching the hallway.)

Poison Dart, Uthek's Demon Trap, & Exploding Rune on the same Search token. Following the rules, for the use of Overlord cards, they must not have the same name, on the same figure, with the same triggering affects. They do not have the same name, but may they be used in conjunction with each other on a single search?

3: May you use a Lucky Charm accessory during the Travel Phase? If yes, is it refreshed prior to it's wearer's first turn?

4: Overpower (Sir Alric Farrow): If you successfully Overpower, and trade spaces with a Hero, may you place a trap on that Heroes' new location and does it trigger?

1: Hero Attacking - If the Hero does not deal sufficient enough damage to deal any hearts to a monster, may they still spend their surge to recover fatigue?

Yes, you can still spend surges on anything, including the general ability to recover fatigue, as long as the attack is not currently missing the target. Dealing insufficient damage is not a miss. The situation you describe is perfectly legit.

If you have insufficient range to reach the target space, then you may only spend surges on increasing the range until such time as you have sufficient range. If you can't get sufficient range, then you miss and all dice are ignored.

If you roll an X on the blue die then you miss flat out. You can't do anything with the rest of the dice. (Note there are some cards in the new Shadow of Nerekhall expansion that do some... interesting things with the blue die's X result. But that's not really relevant to your current situation.)

I've looked around, and there doesn't appear to be any indication that this is or isn't allowed. I think it should follow the same rules as applying conditions, which generally require at least one damage to be dealt.

First of all, removing a condition is not the same thing as applying a condition. There's no reason why the "minimum 1 damage" rule should apply when removing a condition. There's certainly nothing in the rules to suggest that it does.

Secondly, the Holy Power/Prayer of Healing/Cleansing Touch is not part of the attack itself. It was done after the attack was finished, so no damage was being dealt anywhere. The Disciple did two separate things on his turn:

1) made an attack. He recovered 1 Fatigue by spending a surge, but the attack was otherwise ineffectual so far as you described.

2) He used Prayer of Healing after the attack was complete. Among other things, this removed the conditions because of the 3 card combo he had going on.

Poison Dart, Uthek's Demon Trap, & Exploding Rune on the same Search token. Following the rules, for the use of Overlord cards, they must not have the same name, on the same figure, with the same triggering affects. They do not have the same name, but may they be used in conjunction with each other on a single search?

Yes, as long as they all have different names, you can play multiple traps on a single triggering event. Your play was legit.

3: May you use a Lucky Charm accessory during the Travel Phase? If yes, is it refreshed prior to it's wearer's first turn?

I believe so, yes. I'm not aware of any rule that prevents you from exhausting cards during the travel step, at any rate. The card would the refresh at the start of that hero's first turn in the next quest.

4: Overpower (Sir Alric Farrow): If you successfully Overpower, and trade spaces with a Hero, may you place a trap on that Heroes' new location and does it trigger?

There have been a few questions asked of FFG about Alric's Overpower ability recently. I'm not sure if any of them would shed light on this question, but you could check the unofficial FAQ over on BGG to make sure.

As long as the trap triggers on the hero "entering a space" and nothing suggests that it needs to be the hero's turn, then this sounds feasible. I'm not 100% certain though. Traps that trigger "during a move action" would be out though, since the hero is not performing a move action.