The paradox is an almost wholly thoretical problem. Our civilization will never observe even a stellar black hole evaporating, and UMBHs might never evaporate even in the enormously far future limit where their Hubble volumes are effectively de Sitter vacuum.

If a black hole is always colder than the relic and cosmological horizon radiation even as we approach de Sitter vacuum, then it won't evaporate. No evaporation, no missing information -- it's just somewhere else in spacetime.

If a black hole only mostly evaporates, the remnant holds information, and so no information loss paradox. Just a problem about how to assess the entropy.

If a black hole generically isn't no hair (i.e., if no hair doesn't hold up at all, or only holds up in cases like exactly spherical, stationary black holes in true vacuum) then the hair holds information, and so no information loss paradox. Just a problem about the nature of the hair. Hawking, Perry and Strominger are leaning towards "soft hair" as extremely long wavelength particles (wavelengths on the order of the Hubble diameter), and while there are lots and lots of as-yet-unanswered questions in that approach, it is not ridiculous.

There are other possibilities too. This is an issue which has had forty years of study.

The problem is that when you take a _model_ black hole deliberately arranged so that it has the greatest chance of being wholly determined by the eleven free parameters of no hair, and put it in dS electrovac and run that to the far future, so it also has the greatest chance of evaporating, there are a couple of problems.

Firstly, fully classically, we cannot know (because of no hair) if we grew the black hole by throwing in one shell of matter or two shells of matter of half the mass each, or ten shells of matter whose differing masses sum up to the same as the previous two cases. If we don't evaporate, we don't care; if we have a remnant, we don't care; if we fully evaporate, we have lost the information about the number of shells and their individual masses. Worse, when we throw in the shells we have the Hawking radiation temperature rise from T_start to T_end. If we arrange it so that an observer can measure the Hawking radiation as we throw in each shell, that observer will see T_start, T_start+1, ... T_end-1, T_end, so that observer has information that is otherwise lost. So, hair?

Secondly, we can make this worse by turning classical matter shells into individual quantum particles. I need to simplify here. If we throw in two alphas and a handful of electrons, and have no hair, an outside observer will not be able to know if you threw those in, or threw in two 4-He atoms, or 8 2-H atoms, and so forth. The no hair black hole evaporates into photons, and thus you have a version of the Knapsack Problem, with the unfortunate side effect that by the AMPS argument, you must have violated at least one of unitarity for at least some observers, the equivalence principle (in particular the "no drama" condition at the horizon of a sufficiently massive black hole that spacetime curvature is effectively flat at the horizon), the holographic principle (in particular, AdS/CFT's view of it), or semiclassical gravity as an effective (in the Wilson sense) theory of gravitation outside the horizon. People argue about which the worst thing to give up would be, and many qc-gr papers have been written in the past couple of years where one or more is gleefully abandoned, with the consequences followed to logical extremes.

The Hawking-Perry-Strominger approach only deals with the classical problem, hoping to extend that into the quantum realm.

There are several other ideas theirs competes with, many of which start with some quantum view hoping to extend that to realistically massive black holes.

In any event, resolution has proven to be non-trivial.

However, the tl;dr version is that yes, adding in some hair MAY solve the information loss paradox, but there are other approaches, and no good way to choose among them.

Real black holes might indeed be very hairy at all times. They certainly don't live in de Sitter vacuum (or even dS electrovac) today or any time soon, and they even less sit in AdS (and our universe's quantum fields are not conformally invariant). However, these still seem like acceptable conditions for _models_ of black holes where one is probing the nature of the mathematical theories that describe them in detail, and in particular General Relativity.