It probably comes from the relationship the Ninja historically had (and currently have) with Kuji-in and kuji-kiri, practices they developed out of Buddhism, Taoism, Shugendo, Shamanism - basically anything they could find that worked, since they couldn't really be choosy, what with the Samurai breathing down their necks and up their mountains. The Japanese back in their feudal days were very superstitious and the Ninja would capitalize on this to their benefit by employing masks of demons or flash powder tricks, etc. Also, their practices of stealth and hiding would create in the minds of their adversaries fantastic stories of how they accomplished these feats. Besides, think about it - if you were a Samurai and seppuku was the price for failure, which story are you going to tell? The one where the Ninja turned into a crow and flew into the night sky and there was nothing you could do because of his evil trickery? Or the one where the Ninja climbed up a tree pretty damn fast and you missed him in the dark? The whole "Ninja Magic" phenomenon is a good historical example of the snowball effect.