If we accept that black holes do not indeed destroy information and that they follow the second law of thermodynamics (this is how the entropy-is-proportional-to-area formula was derived, after all) then we can forget about their being black holes and simply think of them as some object radiating black-body radiation. From this standpoint, the entropy of the black hole does not have to always increase, rather, it is the entropy of the Universe as a whole that must do so. The thermalised Hawking radiation has a microstate not fully defined by its macroscopic blackbody temperature, so it carries off entropy to compensate for that lost by the black hole. The system microstate before a radiation event is encoded in the black hole microstate and the radiation microstate, so no information is destroyed and the state of the whole system remains fully defined by the whole system state at any other time; otherwise put, the whole system state at any one time is a one-to-one function of the state at any other time.
Now this answer should be qualified by the warning that the so called Black Hole Information Paradox is not held to be resolved as yet by theoretical physicists: so it is not yet clear whether information is destroyed by black hole processes so the full answer is that no one is altogether yet sure what true entropies of black holes are. This question is foreseen to be resolved by a full theory of quantum gravity.
But for now, a plausible explanation is the classical thermodynamic one I gave. After all, as I said, a black hole's compliance with the second law of thermodynamics is how the area formula was derived in the first place.