My players freak out the most from demons/devils. I don't play them as combat bruisers (for the most part), but a corruptive force or pure evil that can claim even the most pure heart. They rarely manifest directly and combat the PCs, but their servents and schemes are far-reaching and omnipresent. Prolonged contact with the infernal results in madness, physical deterioration, and/or mutation- and it is generally accepted that once a person is permanently tainted, his soul is forfeit. Even the hint of infernal involvement freaks my players out.
Dopplegangers/shapeshifters are scary too, especially if they assume the place of someone you know, and over time you begin to be able to tell something isn't quite right. A former NPC traveling companion was taken by a doppleganger, and it took almost 6 months of game time for them to realize what had happened, and that this doppleganger was part of a larger plot involving the replacement numerous people and manipulating political/social events to a certain outcome.
I try to make undead things to be feared as well. Undead per the MM are wusses, so I tend to beef them up by giving them cleric BAB, and DR equal to half their hit dice that cannot be bypassed. In addition, all undead gain Unholy Toughness and Frightful Presence abilities, because they are antithetical to life and are truly unholy blasphemies than can rend the soul and shatter the mind.
And then of course, the "things man was not meant to know" critters. Mind flayers, the neogi, gibbering mouthers, and most abberations fit in this category. I use them as Cthulhu mythos-like entities, which have completely alien thought patters and seemingly illogical motives. They are extremely rare (only used them in 3 out of almost 90 adventures- and in two of those adventure the PCs went looking for them), but they are often in isolated places and very dangerous. I've made hints (but no definite facts) that these entities predate humans and the gods, and that even the gods fear what could happen if they return/awaken/escape their prisons.