1. If the heroes won the encounter, but did not search the search spots, do they allowed to do so after meeting the victory conditions? Same question for the situation when OL wins the encounter.
No, in either case. The heroes have to search the markers to claim the benefits. You could run this as a house rule, if your group is one of those who feels like 2E favors the overlord - this effectively gives the heroes a free 25 gold per hero in every encounter (double for most quests).
2. Syndrael ability: "If you have not moved during this turn, you recover 2 fatigue at the end of your turn". "Have not moved" refers to ANY movement, i.e. if this hero moved by fatigue, it counts as movement for this ability?
I read this as ANY movement - the hero has to end the turn having not left the square they started in.