My thoughts on Deja vu are very similar to firedemon's in relation to energy recycling and the Big Bang theory. I think we are working on the same theory but will explain what i mean in case it has some differences.

I saw a documentary once in which a scientist (i don't remember the exact field nor can i take a guess at what field would specialize in water, chemistry perhaps?) found some evidence that water retained a form of memory/information. If this is true and even water can retain memory then perhaps energy itself is able to retain memories as well.

Then if we add in the theory of the Big Bang (and equally importantly in this case the Big Crunch, where at some point in time the universe will stop expanding and collapse back in on itself) it would suggest that it is possible that there could have been many rounds of Bangs and Crunches leading to the universe being formed and destroyed many times.

Take on top of this a similar theory to Parallel universes/ A Multiverse, but instead of each universe existing at the same time, they follow one after another (i'm not sure if there is already a theory covering this idea, i would assume so although i couldn't find it).

Putting all this together it would be possible to theorize that our feeling of Deja vu is actually a memory stored in the energy we are made of which has been in a similar (if not exact) situation before.

The main flaw in this theory, from what i can see, would be the unlikelihood that energy and particles line themselves up in almost the exact same way with each Bang/Crunch cycle to create a world/universe similar enough to our own that identical (or very similar) events could occur to create Deja vu, especially when you consider that the only reason our universe was formed was due to the random arrangement of matter after the Big Bang allowing gravity to work to eventually form stars, planets and even us.
But then if you followed the theory that time and space are infinite, it would be possible that an infinite number of Bang/Crunch cycles had already occurred meaning that every possible scenario was played out, in which case why is our whole life not one constant string of Deja vu?

Oh, of course. I forgot about that nasty little theory. Sadly the Big Freeze does seem to be more probable than the Big Crunch these days. But i still hold out hope that we are in an endless cycle of Bangs and Crunches, not to keen on the idea that we are destined to end up constantly drifting further and further away from the rest of the universe.

Otherwise perhaps Deja vu is simply energy remembering from a previous human it occupied who experienced something similar? Although there would have to be something in a theory like that explaining how our brain interprets the memory to fit our life (the actual memory was of seeing 2 horse carts but our brain translates it to cars, stuff like that).