It occurred to me in some conversations after my talk that I lost part of the younger audience in the step where I was classifying solution attempts by the strong and weak form of the Bekenstein-Hawking entropy. Rarely have I felt so old as when I realized that the idea that the entropy of the black hole is proportional to its area, and the holographic principle which is based on it, has been beaten into young heads so efficiently that the holographic principle has already been elevated to property of Nature - despite the fact that it has the status of a conjecture, a conjecture based on a particular interpretation of the black hole entropy.
The holographic principle says, in brief, that the information about what happens inside a volume of space is encoded on its surface. It's like the universe is a really bad novel - just by reading the author's the name and the blurb on the cover you can already tell the plot.
The holographic principle plays a prominent role in string theory, gravity is known to have some "holographic" properties, and the idea just fits so perfectly with the Bekenstein-Hawking entropy. So there is this theoretical evidence. But whether or not quantum gravity is actually holographic is an open question, given that we don't yet know which theory for quantum gravity is correct. If you read the wikipedia entry on the holographic principle however you might get a very different impression than it being a conjecture.
The most popular interpretation of the Bekenstein-Hawking entropy is that it counts the number of microstates of the black hole. This interpretation seems to have become so popular many people don't even know there are other interpretations. But there are: Scholarpedia has a useful list that I don't need to repeat here. They come in two different categories, one in which the Bekenstein-Hawking entropy is a property of the black hole and its interior (the strong form), and one in which it is a property of the horizon (the weak form). If it is a property of the horizon there is, most important, no reason why the entropy of the black hole interior, or the information it can store, should be tied to the black hole's mass by the Bekenstein-Hawking formula. If the weak interpretation is true, a black hole of a certain mass can store an arbitrary amount of information.
If Hawking radiation does indeed not contain any information, as Hawking's calculation seems to imply and is the origin of the black hole information loss paradox to begin with, then you're forced to believe in the weak form. That is because if the black hole loses mass then, according to the strong form of the Bekenstein-Hawking entropy, its capacity to store information decreases and that information has to go somewhere if it's not destroyed. So it has to come out, and then one has explaining to do just how it comes out.
There is a neat and simple argument making this point in a paper by Don Marolf, the "Hawking radiation cycle"
"[O]ne starts with a black hole of given mass M, considers some large number of ways to turn this into a much larger black hole (say of mass M′), and then lets that large black hole Hawking radiate back down to the original mass M. Unless information about the method of formation is somehow erased from the black hole interior by the process of Hawking evaporation, the resulting black hole will have a number of possible internal states which clearly diverges as M′ → ∞. One can also arrive at an arbitrarily large number of internal states simply by repeating this thought experiment many times, each time taking the black hole up to the same fixed mass M′ larger than M and letting it radiate back down to M. We might therefore call this the ‘Hawking radiation cycle’ example. Again we seem to find that the Bekenstein-Hawking entropy does not count the number of internal states."
Let me also add that there exist known solutions to Einstein's field equations that violate the holographic bound, though it is unclear if they are physically meaningful, see this earlier post.
While I admit that the strong form of the Bekenstein-Hawking entropy seems more appealing due to its universality and elegance, I think it's a little premature to discard other interpretations. So next time you sit in a talk on the black hole information loss problem, keep in mind that the Bekenstein-Hawking entropy might not necessarily be a measure for the information that a black hole can store.
For a good discussion of these both interpretations and their difficulties, see "Black hole entropy: inside or out?" by Ted Jacobson, Donald Marolf and Carlo Rovelli.