Gareth, I too, appreciate you taking the time to outline your thoughts, and I also agree with some of my peers that I originally raised a hairy eyebrow at basilisks, but in not too long I settled into the idea well enough.
What I like/prefer and think works well enough, without going too far outside the Tolkien palette, is introducing as many different flavors of {stock monster} as you think the system can handle. So for example, what the writers have started with respect to x variety of Orcs is good, and they should feel free to continue that with human adversaries, wolven adversaries, spirit based adversaries, and so on and so forth.
I also think you can exploit the Tolkien precedent for "one-off" style monsters, whether it's Shelob, or "the" Werewolf, or "the" Watcher in the Water, etc. It works partly because it's self-limiting the palette's expansion by not
daring to suggest there is an entire race of these things, but rather just one or two un-recorded abominations that linger from too much exposure to Sauron/Morgoth/darkness, or what have you.
I'm a Beastman player in WHFB, so I have tons of their miniatures, and am easily inspired by them as bad guys (plus I have a never ending supply for use in tactical miniature-style combat). So I had an adventure with my players involving a single minotaur that guarded a mountain pass who required a game of riddles to get through, and
of course failure meant he would eat them! At first I wasn't thrilled with myself for using "Minotaurs" in Middle-earth but my players liked it and spent a lot of time discussing whether he was a single exception or represented an entire race (I never game them an answer

). It doesn't seem too far off the Tolkien-track; Morgoth perverted Elves/Men to Orcs, Trolls from Ents, Fell beasts from Great Eagles, why not "minotaurs" (Bull-Giants, if you will) from the natural animals of Arda? After all, could you not see this kind of language in the Silmarillion:
Now in those days, Melkor sent evil spirits and other Maia that had given over to him their service to lie with the beasts of Arda, and to yoke unto them, and in their wicked deprivations, those beasts gave birth to abominations; half man and half beast. But as with all things outside the thought of Illuvatar, these plans came to ruin, and the offspring that came about from such unions were terrible and willful, having the heads and feet of beasts, unable to be controlled by Melkor, and they pursued their own rages and desires into the dark corners of Arda, never to be seen from again.
A bit apocryphal, but I think it works
That being said, guard yourself against Gygaxian pulp. The minute you start getting into "alien" things; Illithid and Beholders and nonsense like that, then you have "left the path of wisdom".
So, long story short, +1 here for Basilisks.
Could