Is Hawking radiation truly random or we just don't know that it is? First off I am not a black hole scientist and my education is limited to special relativity so please treat this question appropriately.
The way I understand the BH information paradox is that because we think that a black hole has no hair meaning properties that we can observe are limited to charge, mass and angular momentum, and because information cannot be destroyed, the existence of hawking radiation suggests a paradox. And following this there are solutions that information is preserved on the surface of a BH which is the holographic principle. 
However a curious thought arises and that is if the universe really cares about preserving information on a global scale, why is it impossible to think that Hawking radiation just might not random i.e. the radiation leaking out the surface of a black hole preserves information but we are just unable to piece it together due to the vast temporal differences that might exist between radiation that talks about a teapot that fell in? If one collects all the radiation that the BH emitted since its creation to end, one might find the teapot information in it, kind of like finding a birthday in the digits of pi.
I know this poses a difficult theoretical challenge where one has to propose a mechanism that would span the entire age of the universe till its cessation to show that information really is conserved but that's all it is, a theoretical challenge. Maybe it is a viable model that does away the need for a BH having soft hair on its surface and give us a more robust understanding of quantum randomness. 
 A: We have never measured Hawking radiation from a black hole so we don't know if it is random or not.
In Hawking's original treatment the radiation is random, but Hawking's model is a semiclassical model that treats the spacetime background as fixed. There have been various other approaches suggested, many based on the AdS/CFT model for black holes, and in these the radiation is not random but does carry information. Hawking himself concluded that AdS/CFT models were a good reason to suppose that the radiation carries information.
But these are just models, and none of them have been confirmed by experiment. Hawking's model has the advantage that it is based on known and well understood physics, and few physicists doubt that it is basically correct. But the approximations used in Hawking's model may well be responsible for the lack of information in the radiation he predicts. By contrast the AdS/CFT models are based on untested theories and I suspect most of us regard them as speculative at best.
So the bottom line is that we simply don't know whether the radiation carries any information or not.
