The idea of being stalked by some bloodhound whose can always track you down, even if you think you lost it is a scary idea. Of course, the stalker is always scariest if you don't get to see them. Maybe they just make noise every now and then, or a shadow, or leave a trail when you turn around to look sometimes. Even the notion of the invisible Hell Hound from Supernatural could work with this idea. No target to counter attack.
Of course, the stalker doesn't need to be bad to get under someone's skin. Like a real stalker, they could be an admirer, who leaves you 'love' notes. Of course, when one of these notes suggest they were in the same room as you, perhaps a room you heard a noise in and saw nothing, you'll suddenly get that creeping coldness up your neck as you wonder: are they here now?
The nice thing about being watched is, people try to push this thought out of their head instinctive, thinking that'll take away their fear. But in a game, you need periods where player lulled into a sense of false security, in order to have anything to take away and surprise them. With a stalker, the player is all too willing to put themselves in this feeling safe state, even if you try to convince them the threat is constantly there. Any excuse they have for feeling safe, they'll take. So you only need to be inconsistent with when you choose to remove this feeling of safety.
Just remember, eventually the player will prepare themselves to expect finding something stalking them. And this is when you can give them the scariest thing of all for them to find, something they're not prepared for: nothing at all. Let them examine an area in such a way that it must convince them, that they have to be alone -that the room is empty, they've had time to examine it fully, and there is only one path in, and they can see the path leading up to them for a long way, and know nothing has passed through or is coming towards them. Then, as they turn back or take the only advancing route left -bang, they get hit from behind as it was there all along.