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.
I've never bothered to really look into the BH information paradox (ie I might be missing something that's obvious to all those legions of theoreticians that have), but just from a cursory examination, it never made sense to me. The no-hair conjecture really only applies to stationary BHs, so once you introduce Hawking radiation, the conjecture evaporates right besides its subject.
The analogy I've come up with to illustrate my point is the 'thermodynamic information paradox':
An isolated system will tend towards a stationary equilibrium state, uniquely described by just a few macroscopic parameters. This is our version of the no-hair conjecture.
Now, instead of a completely isolated system, we allow interaction via absorption and emission of radiation. We assume that no matter the incoming radiation, outgoing radiation will obey totally probabilistic thermal laws as there are no hairs. Now, if we were to radiate away all energy (eventually reaching zero temperature), information will have been irretrievably lost.
However, this is clearly nonsense as it tries to apply conclusions drawn under idealized conditions to non-ideal situations: Real thermodynamic systems fluctuate and have hairs. In fact, outgoing thermal radiation necessarily disrupts equilibrium, so the whole question is ill-posed.
As I said, isolated black hole solutions are there to probe the UV end of General Relativity, rather than to act as practical astrophysical models. (We have those too, fwiw).
Hair or not there is _enormous_ entropy in black holes that have not yet evaporated. Since we are fairly sure that no physical black holes in our universe have evaporated or are likely to evaporate in the next 10^65 years (for the smallest extremely isolated unmerged stellar black holes), and black holes deep inside galaxies will be around much much longer, it is perfectly reasonable to ignore the outgoing radiation and say that black holes are _effectively_ bald until our eventually much bigger Hubble volume is much closer to de Sitter vacuum. Indeed, mergers of black holes in nature are expected to undergo rapid "balding" as their complicated dynamical modes decay. So I can't agree with your last paragraph.
It's relevant to consider the origin of the Hawking radiation. Differently accelerated observers looking at a region of a QM field that's in thermal equilibrium will disagree on particle count. The formation of a black hole horizon creates a dynamical spacetime in which there is an acceleration between past observers (before the horizon forms) and future observers; the future observer sees particles within a few Schwarzschild radiuses of the black hole that the past observer does not. We usually consider a photon field for simplicity, but the particle count difference applies to all matter fields generically.
These particles are effectively created by fossil curvature which classically puts them on complex geodesics that go to infinity. In departing the region near the black hole their contribution to the local energy-density drops, which dynamically shrinks the horizon area. That in turn reveals previously hidden fossil curvature (which runs all the way to the singularity), which again is equivalent to an acceleration between past observers (before the "shrink") and future ones (after the "shrink), with the latter seeing particles that the previous ones do not. Voilà: evaporation, provided that nothing replaces at least the energy density of the escaping Hawking radiation particles (since that increase the area of the horizon, hiding behind it some of the previously observable-outside-the-horizon fossil curvature and thus some of the dynamic production of particles).
The quantum picture is slightly different because the particles are extremely low energy, with wavelengths proportional to the curvature radius at the horizon. "Soft hair" makes sense when one realizes that the curvature at the horizon of supermassive black holes can be arbitrarily flat (i.e., you can in principle have particles with wavelengths as long as or longer than the Hubble length). That's a very different picture from fully classical pointlike particles. However it's not clear that that's sufficient to dent the enormous difference between the number of microstates inside the horizon and the eleven variables of the macrostate of a no-hair black hole.
Additionally, even if it did wipe out much of the black hole's entropy, there does not yet seem to be a way to unitarily evolve from pre-horizon state to fully evaporated state; the details of what exactly was in the black hole as the horizon formed and what drifted in later are not obviously encoded in "soft hair", and the assumption is that the encoding would involve strong gravity somehow (and it must as the horizon area gets small).
So even taking your idea of adding a bunch of additional macroscopic parameters to no hair's eleven (at a particular time coordinate), you still have a non-negligible fraction of a galaxy worth of mass inside the horizon of an SMBH that fits comfortably within Jupiter's orbit, and absent a quantum gravity theory you'll have little idea about how to count all the compatible microstates. The information loss you are blithely accepting in your second last paragraph is difficult to conceive: for a spherically symmetric black hole of merely one solar mass the horizon area is about 10^77 in Planck areas, which gives us the holographic entropy bound. 10^77 is greater than the value of S for all the gas, dust and noncompact stars in the Milky Way.
(Finally, I want to note that there are of course many approaches to the post-AMPS black hole information problem very different from Hawking et al.'s "soft hair"; however super- and ultramassive Schwarzschild black holes in dS vacuum are good model probes of each of these possible theories).
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.