Argyle King
Legend
Conan is regularly defeated, even if he can't die for plot reasons. Sometimes even just he's sneaking down the corridor and some mook guard sneaks up on him and knocks him out -- so he can wake up in a prison cell and romance the evil king/warlord/necromancer's beautiful daughter/assistant/etc. I don't know if I'd call it Deus ex machina, but it definitely qualifies as protagonist-centric-outcome (unimportant people in the same situation would be executed before they woke up).
Right, I agree with that. He's still presented as someone who can (and does) fail.
While his immense skill and prowess might help insulate him from failure, he's never presented as immune to it - even when it's mundane.