Maybe a Black Hole destroys information, or perhaps it changes information to a form that we can't (yet) recognize. Presently, both of those states would look the same to us.
Did you have something specific in mind? Otherwise as I read your comment I should mention the 'recognizability' of the information is irrelevant to the paper. The paradox is about the differing predictions from general relativity and quantum mechanics, one of which implies that the information is lost and the other of which implies that the information is not (the form it takes is not important).
I was wondering this about empty space / dark matter. Maybe it's just we're blind to it so far, because assembled in a context of things sensitive to a specific blend of forces.