Under broad assumptions, breaking of Lorentz invariance in gravitational theories leads to tension with unitarity because it allows for processes that apparently violate the second law of thermodynamics. The crucial ingredient of this argument is the existence of black hole solutions with the interior shielded from infinity by a causal horizon. We study how the paradox can be resolved in the healthy extension of Horava gravity. To this aim we analyze classical solutions describing large black holes in this theory with the emphasis on their causal structure. The notion of causality is subtle in this theory due to the presence of instantaneous interactions. Despite this fact, we find that within exact spherical symmetry a black hole solution contains a space-time region causally disconnected from infinity by a surface of finite area-the "universal horizon.'' We then consider small perturbations of arbitrary angular dependence in the black hole background. We argue that aspherical perturbations destabilize the universal horizon and, at the nonlinear level, turn it into a finite-area singularity. The causal structure of the region outside the singularity is trivial. If the higher-derivative terms in the equations of motion smear the singularity while preserving the trivial causal structure of the solutions, the thermodynamics paradox would be obviated. As a by-product of our analysis we prove that the black holes do not have any nonstandard long-range hair. We also comment on the relation with Einstein-aether theory, where the solutions with a universal horizon appear to be stable.