I'd agree that Israel faces all three of those problems plus the obvious geographic and demographic problems. Thus, seems to me that legitimacy of a Palestinian government is one of the more minor deterrents to the making of peace.
...The norms are specifically concerned with human rights, free market principles, and democratic governance. States which act in contradiction to those norms are not simply discredited, but criminalized to the extent that their political sovereignity is less measured by traditional means and increasingly more measured by those Western norms. Consequently, I think there's an "anything goes" attitude in regards to those states, akin to "Indian Country". This is not to say that states do not routinely undermine and challenge one other's sovereignity, but that the West is actively undermining the legitimacy of states in ways which I think prohibit effective diplomacy, and to a lesser extent, warfighting.
I believe the problem is one of western arrogance, not so much "anything goes" as a 'they are not behaving properly and should be corrected.' Nanny stateism to the sixtieth power. It's not undermining legitimacy so much as it is a discounting or, more correctly lack of knowledge and ignoring of the differences.

The Formal Surrender Document is a good example; among western states such a document would have meaning -- in the ME, documents mean little -- unless the Middle Easterner knows you will adhere to the document, then he'll use it for all its worth against you while totally ignoring those aspects that pertain to him that he wishes to flaunt. Paper and treaties mean nothing, what occurs under the table and behind closed doors is what's important; surface pronouncements and agreements are mostly obfuscatory. Recall, this is an area where items in stores and markets do not have a price tag; haggling is a national sport and in such haggling hyperbole and even outright lies are encouraged and expected. Most in the west do not understand that and thus tend to think ME Folks are dishonest, etc. They aren't bad, just different -- and the lack of knowledge in the west fuels an apparent delegitimacizing (new word...).

The impact on warfighting is minimal to non-existent, it complicates diplomacy but does not prohibit it. The diplomatic problem is that ME specialists can try to tell their western political masters about the nuances but said masters have massive egos, power and obviously are omniscient -- so they ignore the knowledgeable people and make stupid decisions.
...but I do think it would have inhibited it to some degree dependent on which Iraqi authority announced a formal surrender and which Iraqi factions were loyal to said authority. Then again, with Saddam elluding capture for some time, it may not have been possible to attain or create a "legitimate" Iraqi leader to announce a surrender.
Saddam was the government; there was no other authority. Such a surrender wouldn't have made any difference and in any event, there would not have been one because Saddam's two Russian Generals gave him some good advice -- "You cannot beat the Americans, so have your Army melt away before them, turn to guerrilla warfare and they will tire and leave soon so you can resume power." We missed it initially but on that last, 'leave soon' -- Fooled them...