Monolith have released an official statement on the matter thus:
The Nemesis System is designed to allow for orcs to survive tough encounters, despite the player having defeated them in battle. Players may see captains or warchiefs who appeared to have been killed return with battle scars specific to their last encounter. For example, an orc who was slain by a headshot from an arrow may return with a metal eyepatch indicating he's lost an eye; or an orc who was burned in a fire may return with burn scar-tissue on his face; or an orc stabbed in the head may be covered in bandages. The only way to ensure an orc does not return is to decapitate him in battle, which occurs using certain combination moves. If an orc is not decapitated, despite having the appearance of being killed, he may survive the fight and return to battle later on in the game.
The Monolith team has received player reports of decapitated orcs returning from death but in internal testing have yet to be able to recreate an instance of a decapitated orc surviving.
Could that last sentence suggest that Monolith doesn't believe us? It's funny if they don't because Gamertroll can assure you he DID have to kill a particular Orc three times. It's beyond doubt: the first time he got run through, the second time Gamertroll made a point of chopping the sod's head off. Sure enough he turns up again with his bloody great shield and a chunk of plate metal stuck in the left side of his skull - would recognise him anywhere. Would you believe he even had the cheek to erroneously state that it was him that had killed me at our last meeting?
Had to chop his head off again. Touch wood, he hasn't come back a 4th time.
If you have trouble with a particularly difficult Orc that won't stay dead, you could try this is Monolith's advice. Good luck, Gamertroll had to do use the Chord method twice to dispatch his.
If an Orc is not decapitated he can be scarred but cheat death and return to face you again. He should acknowledge this in his Showdowns and VO. This isn't like Talion where it is supernatural, it is just a result of them being extremely tough. You can decapitate a Captain by either
Using a Chord (Triangle + Circle) when your Hit Counter is charged or Dominating him and selecting "Kill"
Whatever happens with this weird glitch, it takes little of the shine from this superb game. Gamertroll gave it a massive 8.4/10 thumbs up - you should play it.
Gamertroll was going to write an article on PSN network's continuing issues but realised that the problems with Sony's beleaguered game network are now so constant, that it it would only be real news if PSN managed to work for more than three days in a row.