Well, another possibility is that information is not conserved. Conservation laws have turned out to be false before (CPT, I'm looking at you!)

Now, Nöther showed that every conservation law corresponds to a symmetry, but I actually don't know what symmetry corresponds to conservation of information, or why it's necessary.

I defer to your much greater knowledge here, of course.