How does déja vu, that is the re-experiencing an experience, fit into this theory? It appears that the Information axioms fails to be Essential when one considers déja vu.
I don't see that deja vu poses a problem. Deja vu is simply a feeling of familiarity associated to an experience. It doesn't involve actually having an experience more than once.
Possibly - but I could just claim that for me déja vu is exactly when two experiences are not differentiable from one another. And if someone claims to have experienced this moment before, identically, how would I refute their claim. It's their experience after all.
When I experience deja vu, I can never place the time or location that I actually had a previous similar experience. Nor can I predict in advance any occurrence, despite it seeming so inevitable when it does occur. It is simply a dreamlike quality of familiarity. Having done some reading about it, this seems to be the typical state of affairs.
Given this, the simplest and most compelling explanation is that the brain has somehow short-circuited itself into invoking a sense of familiarity. Otherwise I'd expect, at least some people, some of the time, to be able to either link the two experiences or make predictions. The claim that exactly the same experience has actually occurred twice is the more remarkable, both in terms of evidence and plausible mechanism.
Whilst I do appreciate that experiences are highly subjective beasts, it doesn't feel like this really challenges the linked article. Besides, if one is so wedded to the subjectivity of experience, they might as well just say that nothing can objectively explain consciousness because it's subjective, end of.