The above statement should probably be heard more often than it does. After all, even though the PCs are the heroes in an adventure, it doesn't mean that they should be able to walk straight over any creature they may encounter. 5% of all encounters should be overpowering, but once a DM throws such encounters at their players, what he gets in return is often complains. I hope that what you find below may help in bringing more terrifying encounters to life, whether the PCs are able to overcome them or not.
Show them what it does
Before we get to the different encounters, it should be mentioned that showing the players what a creature can do before they actually have to face it should help put some fear in them. There are several ways to do this:
You can show the players the results of an earlier attack by the creature. If you want the players to know the power of a dragon, let them come to a city that has been attacked. The devastation wrought by the creature should tell them that this creature should be taken seriously. You can have a commoner tell them that it was a dragon, or the players could try to figure this out for themselves. If you choose the latter, just remember that it should be obvious once they encounter the beast that this is the attacker. Having someone point out how much time was used to bring about the result may add to the terror.
Alternatively, you may have the PCs present during the attack. That way they can see the attack for themselves and may gain some information about the powers of the attacker. The PCs may decide to attack the creature if they get the opportunity (as will many npcs as well), but the creature should pay no more attention to them than anyone else. They may suffer a random attack as the creature passes by, but killing the PCs should not be the creature's goal (at least not yet).
In some situations you may show the power of a creature by having the PCs witness it defeating a creature they have fought themselves. To use an example from the new King Kong movie, if the PCs have fought a tyrannosaurus, and now see one (or 3!) being defeated in combat by another creature, it gives an indication of that creature's power. Note, however, that for this to yield the desired effect, the PCs must have fought the tyrannosaurus quite recently (or the battle must otherwise be memorable. If they don't remember the fight, it will not have as strong an effect). Also, the battle with the tyrannosaurus must have been quite tough. If the party easily defeated a tyrannosaurus, having King Kong doing the same will not be very impressive.
Now to the encounters.
Deep Rising: Defeating a creature bit by bit
If you want to use a creature like King Kong, Godzilla, or the creature from Deep Rising, you should not force the PCs into a straight combat against it. If you do, they will surely lose. Rather, you should do as mentioned above: let the creature's goal not be to kill the PCs, but something else. Dungeon Magazine has used creatures like this at least twice, in «Lord of the Scarlet Tide» (#85) and «Beast of Burden» (#100). In this case, defeating the creature should not necessarily mean the PCs have to kill it.
«Defeating» the creature could mean that the PCs have to hold it off for a few rounds until the banishing ritual is finished, the defenses of the city is in place, or the summoning spell expires.
Another option is to have the PCs encounter the creature several times. Each time they only fight it for a few rounds before they (or the creature) withdraw.
A third option is to use several weaker creatures as pieces of a bigger one. In Deep Rising the creature uses its tentacles to attack the people on the ship. In the same way, you can use worms or plants to account for the tentacles or roots of a larger creature. Obviously, this option does not work for all encounters.
Jurassic Park's Velociraptors: One too many
As mentioned above, players often take for granted that they will be able to defeat whatever the DM throws at them. He may want to show them that there are some things out there that they can't defeat, but if he throws an overpowering encounter at them, they may complain that it isn't fair. On the other hand, if the DM lets them defeat everything he throws at them, this will not help reducing their ego.
Individually tough opponents may solve this problem. A zezir (MMIII) has a CR of 6. This means it should be a very difficult encounter for a party of four 3rd level characters (although they should be able to defeat one). Raise the number to two, and the EL becomes 8 – an overpowering encounter for the same party. Now they should run. By switching between one and two zezirs (in different encounters), you can switch between doable and overpowering encounters. The same is true for groups of several creatures.
Stargate SG-1's Replicators: When swarms attack
In this case, swarms refers to a large number of creatures, not only creatures defined as swarms (that is, creatures with the swarm subtype). Not only their numbers may be of importance here, but if the swarm seems endless, it might make the terror greater as the players realize they can't hold the swarm off forever. A creature like Godzilla may be bad, but the terror should be no less at seeing a carpet of spiders (or other creatures) overrunning a city.
I'm probably going to use some of those, but you forgot to add the roleplaying tension. A creature can become fearsome through its appearance. If you described an ogre like this, most parties would think twice before attacking.Before you stands a creature of at least twice a normal man's length. Its muscular body seems able to crush anything but the strongest stone. The fierce jaws can crush a head with a single snap and the huge club it wields could probably pummel you all into pulp.
Well, without getting too gruesome, she was murdered only recently. I described the gauges in the stone walls as deep as your hand is wide, how the hardwood furniture had been torn and sundered like so much origami. "It appears" I told them, "that a tornado hit this room. That's what happened to solid stone and oakwood, I'm not going to describe what happened to the body". The looks of total, abject shock were worth all the effort I put into thinking through the description (it was a good but longer than I have summarized here). However, I think that this may have hardened the players against the murderer, they are in disagreement as to thier next move, but I believe they may still go after him! If so, I'll have to use some of these other tips to help them avoid a TPK.
(The "monster / demon" that they are envisioning is really a half-orc frenzied berserker wielding a +1 vicious, adamantium spiked chain, each link is sharpened like a blade on each side, and the chain is draped around him, painfully cutting into his flesh. The effect is much like a chain demon, which I have done intentionally to keep the players guessing.)
And, what I always find to be important: Do not use numbers, but descriptive. "The guy is 3 metres tall" makes the players think "about one metre more than I. That’s not much." "The guy stands as tall as this room" provokes another reaction entirely...
Cifer: I hadn't thought of what you mentioned in the last part of your post. Thanks for pointing it out.