Well, let's start out dividing high-level monsters into those who got there by virtue of their enormous size, and those who are a more reasonable size but super specially tough and magic.
Those latter creatures - vampires, beholders, liches, dragons, demons and so on - have loads of spells, powers, and attacks to justify their challenge. Fighting them should be harrowing, not boring. If it's boring, what are you still doing playing the same characters? Are the so tricked out that they make every saving throw, dodge every attack? After the beholder should there come the uber-beholder, in an ever-swelling progression of N+5 hit dice? Maybe in a computer game, or an RPG that needs to sell more and more game books to the power-mad adolescent mentality. But anyway, that's a different topic.
Now, you get the big, big monsters at risk for being boring in the mathematical sense, with lots of hit dice and not a lot of special gimmickry. Not sentient, so they don't come with cool stuff like allies or siege engines or tactical setups. Big lumpy things like ... er ... dinosaurs. And mammoths. Elephants, too. Whales?
|Not the only way to add interest value.|
Those aren't in the rules as written? So what! You're playing old school and it's your game. Later editions sure as hell try to build this kind of special excitement into every monster, calling them special attacks or feats or daily powers or whatever. You, too, at every level of challenge, should be thinking what makes this creature's fight different. A guy with a sword, even the most magical sword, shouldn't be able to bring a dinosaur down even after hacking at its left toe for ten minutes. Make them do something dramatic for the kill, use the climbing-on rules, run and jump into its open mouth. Treat the combat as a living riddle, not an exercise in subtraction, and your players will feel they're working for the kill - not just adding escalation factors.
Okay. My campaign begins again on Saturday (and then immediately goes on hiatus for three weeks as I gallivant about stateside.) I doubt any dinosaurs will come up, but you never know.