I am struggling with this quest, was someone able to do it single-handed? Tried different decks, but I couldnt manage to win.

I play single handed and i remember after many tries not being able to beat this one as written , i play normal level mostly as i do not like to remove encounter cards if i can help it. There is easy mode of course to go to but i think even with extra starting resources it was too hard.

My usual way of dealing with harder quests is to look at the trigger cards and see where a single player gets a raw deal - in this case it was the Uruk Chieftain who engages the player with the most orc enemies - which is always you of course, almost every round. I think i found the scenario more fun by only triggering this particular chieftain engagement after the last quest card was revealed. I kind of used him as a final boss figure, and I do not remember this being that easy even when i had made this rule change.

I like deck tweaking, but do not like deckbuilding a whole new one specifically to have to beat a scenario really, so i rule adapt to try and compensate for a single person. Sorry it doesn't really answer your request for help on a winning deck.