As has been mentioned here and there, one of the problems widespread among long term gamers and long term campaigns, is a certain loss of feelings of wonder and mystery. These feelings, which are so important when we enter the hobby, fade over time as players become familiar with the game as it is documented (i.e. they read the rules). No game element is more likely to go stale than are monsters.
Here’s a typical situation: a party of adventurers encounters a troll. The characters have never seen a troll and have no in game knowledge of the troll. However, the players know all about the troll, because they would often look at the troll entry in the 1e monster manual, usually during post succubus picture jerkoff afterglow. What do you do in this situation? The gaming situation, that is; your sick fascination with succubus is your own fucking problem. Freak.
Well, I was asked "the troll question" by a fuming gamer buddy a couple of years ago. He had been hosed by the referee for trying to use meta-game knowledge of the troll, and then got frustrated when he was barred from burning the troll up because his character wouldn't know enough about the troll to pursue this course of action.
He asked me how as a referee, I would deal with such a situation.
My answer: I wouldn't deal with the situation at all- because it is never going to come up in one of my games. Never.
At best, this sort of problem is the product of poor, lackluster lazy refereeing, or, at worst, actively antagonistic refereeing, either way the players are NOT at fault. This is the reff’s problem.
Allow me to elaborate- a skeleton is obviously a skeleton, BUT a troll is a big slobbering green humanoid thing. If the characters know enough to call it a troll, they should probably be hip to the regeneration. If they don't know enough to call it a troll, then they probably aren't going to be hip to the regeneration thing either. In the latter case, the GM shouldn't say "it's a troll!" he/she should use a little imagination and just give the players a description.
"A giant green man-thing, covered with leaking boils and stinking of rotten meat, lumbers towards you out of the darkness,"
Better still, give the creature a story and a name:
"Seek you Greenfang the Maneater who lives in the blackened stump of the Blood Tree on the Bone Mound,"
Both methods are better than, "uh... there's a troll...uh... and he, like, lives up on a hill just outside of town. You guys want to go after him?" in a whole bunch of different ways. However, there are other things you can do as well, which I'll touch on below- but, in a pinch, these two could do it.
Moving forward, I am going to divide creatures into two separate categories from here on in- critters and monsters.
Monsters and Critters, there's a fucking difference:
Critters are run of the mill examples of a species. A wolf, a gelatinous cube, an ape, and a human are all examples of critters. Monsters are individuals- although, they may be (but are not necessarily) members of a critter species, something sets them apart. A vampire is a critter; Dracula is a monster. A whale is a critter; Moby Dick is a motherfucking underworld/sea ruling motherfucking monster. I hope the difference is clear. More on monsters below; first, though, I want to talk about critters.
Once things were different, but time has passed, and today critters taken from most of the original D&D source material are currently about as fresh as a fifty-year old dockside whore. Enough about my mom, though; lets move on. So, if we accept the fact that most every critter in the original game holds no surprises, we also accept the fact that we can’t really, for the most part, use them any more- and we certainly cannot use them “as is.” So what are we to do?
Check this out:
AC: 9  Special: radiation
HD: 2 Move: 13
Attacks: bite HDE: 2/ 30
Similar in appearance to a trilobite, the trilon is a mutant arthropod about the size of a dinner plate. Its bite is radioactive; anyone bitten must make a saving throw (+4 mod to their roll) or contract radiation sickness. If untreated, radiation sickness will lead to death in 4 days -25% hit points each day.
I originally posted the above here. That doesn’t matter, though, what matters is that it started out as standard Swords and Wizardry White Box Small Giant Centipede.
Armor Class: 9  Special: poison (save): +4,
Hit Dice: (1d2 HP) Attacks: bite:
Move:13 HDE/XP: 2/30,
Giant lethal centipedes of the small size inflict a lethal amount of poison with a +4 modifier to opponent’s saving throw, but inflict no damage if the saving throw is successful.
See how easy that shit is?
More than one of the entries in the post linked above was created the exact same fucking way. How many exactly? I don’t know, i honestly can't remember. Once I change them, they’re mine.
So here’s a simple way to go about this. Take a monster, think about it in regards to your setting. Make some changes that make it fit your setting better. Make it stronger or weaker or stranger. One thing I like to do is list out a bunch of special powers, like the troll’s ability to regenerate or the dragon's breath weapon, and give them to otherwise unaltered critters. Wolves are kind of boring. Wolves with the banshee’s save or die scream instead of a normal howl are an awesome motherfucking surprise.
I think the kids call this kind of thing re-skinning, but fuck them they don’t bear the shame of having paid real money to see Breakin’ 2: Electric Boogaloo, so they don’t know shit about pain. You do, though; use that knowledge at the table.
Now on to monsters:
Monsters are, as stated above, singular entities. They are, for the most part, unique. Not only are they unique, they should be, at the very least, the focus of at least a session. Monsters are all about stories. A monster has a story, often an origin story, which is usually some what tragic. This story should be, if not well known, at least rumored at, and should contain hints as to how the monster can be destroyed or warnings about the monster’s powers or information about the monster’s lair. What the players chose to do with this information will create another story.
An example from classical mythology and stop motion films is The Medusa; like her two sisters, she was both a critter (a gorgon) and a monster. Persius used details from her story to slay her, a task which required some special gear and (in the movie Clash of the Titans, anyway) gave him the juice the take on the Kraken (Cetos). Harryhausen movies are a good place to look for monsters, btw. The monsters are all unique and the fights with them are usually groovy set pieces that often require the hero to come up with a unique solution.
Here’s a monster from my last Metal Earth campaign:
AC: 0  Special: see below
HD:14 (84 hp) Move: 20/ 22 (when jumping)
Attacks: Bite, stamp HDE:11/ 1700
The unkillable is a giant (about three times the size of an elephant) black goat that terrorizes the island of Skeeme. It emerged one day from the shimmering blue wastelands at the southern end of island and has been on a more or less continuous rampage ever since. The islands residents, regardless of their potency all fear the beast and regard it as a force of nature, with an almost divine level of power.
The Unkillable hates everyone and everything, living only to kill and destroy. In addition to its bite and stamp (1d6 each), The Unkillable can breathe fire 3 times a day in a 45 foot cone, 15 feet wide at its base. Anyone caught in the cone takes 3d8 damage, (1/2 damage with a successful ST).
The Unkillable is immune to normal weapons and can only be harmed by magical or energy weapons.
It can also jump 100 feet horizontally and 30 feet vertically.
This monster is nothing more than a modified Devilgoat- a critter made up based upon some memories I have from doing farm work as a kid. Point of information- goats are assholes.
AC: 2 
Special: breathes fire, ram
HD:9 Move: 20/ 22 (when jumping)
Attacks: Bite, stamp
Huge, intelligent and evil predators. Devilgoats hate everyone and every thing. They live to kill and destroy. In addition to their bite and stamp (1d6 each), Devilgoats can breathe fire 3 times a day in a 45 foot cone, 15 feet wide at its base. Anyone caught in cone takes 3d8 damage, (1/2 damage with a successful ST). Devilgoats can jump 100 feet horizontally and 30 feet.
Anyway, hopefully you get he general idea of what I’m trying to say here. If you don’t feel like doing it yourself (really, though, how hard is it to quadruple a skeletons HD, give it burning red eyes, a sinister blue radioactive glow, the ability to jump like a flea and regenerate?) there are resources out there you can draw on. My understanding is that Jim Raggi’s Esoteric Creature Generator is a fine product, for instance. I haven't bought it because I like doing this sort of thing myself.
Beyond that, 2e AD&D had a shit ton of monster books released for it- my personal favorites are the two for Dark Sun, they’ve got all kinds of crazy dangerous shit in them, which you could easily alter a bit and use.