<exigentsky>
I've been playing the KID for many years and IMHO it is completely sound in all lines. I'm sorry that I have no experience in the NID/QID.
Anyway, several instances along the line I had met many challenges against the KID (which as you said, are the Bayonet and Fianchetto, among other lines) so I had my share of doubt against the opening. Yet, each time, I came back to the KID. I believe the NID and QID combo is also completely sound and in NID's case, very complex and interesting. However, I was especially put off by the QID, which seemed to me as an obtain-equality-and-draw opening. So...
I scurried back to the KID and worked harder on it. For me, the biggest headache was the Bayonet. Even though in the Fianchetto White seems to be able to get a solid-with-potential position out of the opening in the mainline, this is often an illusion and White can easily find his world blowing up into pieces. This can be proved by games by many KID champions. Off the top of my head, Zita vs Bronstein is a famous example.
In addition, Black can also deviate earlier and use other ways to create chaos. (For this I recommend "King's Indian Battle Plans" by Andrew Martin: it is not very well-organized but it gave me a lot of ideas and inspiration.) In passing, I must also bring you to notice the fantastic book by Gallagher, "Play the King's Indian" in which it demonstrates the power of the Gallagher variation against the Fianchetto, which utilizes several ideas from the ...exd4 mainline along with its trademark ...c5 and ...b5-b4. Although Gallagher himself confessed that he does not play the variation anymore (he became disillusioned with it after everyone started to prepare a special setup against it), it does not mean that the so-called refutations are concrete. In fact, there is room for improvement and this goes for all the lines. (Remember Kasparov also became disillusioned due to the Bayonet and look how easily Radjabov cleaned up his opponents in the variation earlier this year).
On the topic of Bayonet, until last year everyone from superGMs to amateurs like me thought the KID was just the Bayonet's whipping boy (it just wasn't fair

). Then the angel Radj came and poured destruction on this so-called KID-killing-kryptonite. Everyone saw his method: be versatile, just rearrange the pieces, win the weak e6 pawn and maybe still get the KID kingside attack! Inspired by this, I went and did some new thinking and concluded that Black can actually safely win that pawn in many lines (though via different manoeuvres and after a bit of preparation). So now I again play the KID with full confidence. Your oppenents surely are merely "booked up" and against your deviations or secret and devastating improvements in the mainline, more often than not they will fall to bits.
Before I finish this lengthy post (I'm sorry that I wasn't able to be more concise

), I share with you my opinion that actually the Saemisch can prove quite a hurdle and the ...c5 gambit in the theoretical books is not actually as safe as they might make you think...
Good luck with the KID!