As an owner of the gold cart, I can verify that OoT in its original form is substantially more violent and graphic than most E-rated games I've played. In fact, I'd say it's almost up there with the Teen-rated Goldeneye in terms of violence, though Goldeneye has enough blood in it for an M rating. Of course, the frequency of "violent deaths" is much less in OoT.
I get the impression that the ESRB was much more lenient back then, before graphics got realistic enough to really be disturbing. Even Goldeneye seems like it should have warranted an M rating, looking back and considering that the less violent Halo (where you spend most of your time shooting aliens and green-blooded zombies, if I remember correctly) somehow earned that score. I strongly believe Ocarina in its original form deserved a Teen rating, not only for the blood and violence (which was substantial) but also for the dark themes and the downright frightening moments. The bottom of the well, with enemies like the dead hand, was substantially more scary than, say, the ghost house in Mario 64 or Mad Monster Mansion. It was disturbing on the whole. I like this.
So yes, in the end, it deserved a Teen rating more than any other Zelda game. While I don't mind a childlike approach in such games as The Wind Waker, I think it was all the better before it was censored, and its edginess gave it its sheer power. The blood added to this. Drawing Ganon's blood in the final confrontation--when you plunge your sword straight into his face--was immensely satisfying and powerful. It felt heroic. Drawing green snot in the newer versions did not.