No, when I suffer from Sleep Paralysis, it’s always in the middle of a nightmare. Or the beginning of one. Often, there’s a demon or murderer in the room with me, walking very slowly and smiling. The only time that it wasn’t terrifying, and “woken up” unable to move to find a little Terran base on my chest. Pretty quickly, some Hydralisks un-burrowed themselves and began attacking it. At that point, I decided that I played <I>way</I> too much StarCraft.
I used to suffer Night Terrors pretty often as a kid. I’d have them so often that I constantly had (and occasionally still have) a fear that I’m going to turn around and some evil creature or person will be standing there, and then I’ll have to wake up gasping for air. I don’t fear the creature standing there, I fear the waking up afterwards.
The actual reasoning behind deja vu, Steve, is that the mind is slow to register an event as having happened, so you see it, and then your mind registers it as an experience of your own… giving you the feeling you’ve seen that event happen before… (or something quite along those lines…). It’s actually no foretelling, (unless you dreamt an event prior to the moment, in which case it technically isn’t deja vu)…
People don’t really know why this happens. Tiredness is though to be a big contributor, though.