I have experienced a fair bit of deja vu personally, although it's usually more of a passing feeling, and not quite so creepy. But I have had one or two very shocking ones (walking into a place I hadn't been before, but had remembered dreaming about) and it is unsettling.
Can't really explain it, other than I read somewhere that when you're dreaming your brain fills in the gaps between the realistic information with other sort of speculative information to paint the full picture. Sometimes it doesn't do a very good job, and that's why you find yourself at work, but with it attached to your mom's kitchen or some such nonsense. It would stand to reason that someone whose brain is better at capturing/retaining information would do a better job at filling in realistic details and creating more waking situations that seem very familiar.
