The patent is about representing documents with markup (XML or otherwise) not by embedding them in the text, but rather having them stripped and maintained as a separate list of (tag, position) pairs, with the document only containing the raw text.
I'm only surprised that Microsoft couldn't find prior art, because having a (content-type, address) index at the beginning of a file is not exactly an unusual representation. It also reminds me that the USPTO's idiosyncratic usage of non-obviousness doesn't really match my intuition.