I'm not too qualified to speak about the Black Hole Information Paradox, but I think I can say a thing or two about Maxwell Daemons. I think the essential "flaw" in your description is the assumption that Maxwell Daemons destroy information. The do not, and I describe what they actually do in my answer to the Physics SE Question "How can the microstates be measured with zero energy expenditure?".
The essential idea is that a Maxwell Daemon must observe the state information of gas molecules in order to work. So it transfers information that was formerly encoded in the physical states of the heat reservoir into the internal states of the Maxwell Daemon. Indeed we can and actually have built a working Maxwell Daemon in the laboratory (as discussed in my answer) and it is a simple finite state machine. So the state information in the heat reservoir and gas becomes encoded in literal computer memory and it is not "destroyed".
Ultimately a working Maxwell Daemon, whether a living, conscious brain or a simple three-state computerised Maxwell Daemon of the kind we have actually built, must erase its memory otherwise it will "fill up". But the physics that describe computer memory erasure is, at the microscopic level, perfectly reversible. This means that, if we could measure the precise and total quantum state of the computer straight after memory erasure, we could in principle run a simulation backwards in time beginning with this state and infer the state of the memory before erasure.
The last paragraph is simply a long winded way of saying that the information contained in the Maxwell Daemon's memory is transferred to and becomes encoded in the state of the matter making up the computer's environment. One way matter can encode more information is by heating up: if you approximate it as being made up of quantum harmonic oscillators, each oscillator accesses higher and higher energy states, thus its state ranges over a bigger "alphabet" as the system's mean energy increases. The mere fact that the Maxwell Daemon cannot destroy information shows that it must become more and more thermalised. This is how it complies with the second law of thermodynamics: at some point, work must be done both to allow this access to higher energy states ("heating") and to remove the heat to keep the computer from e.g. melting and failing.
The Maxwell Daemon conforms with the second law by dint of the work that must be done to throw the excess entropy - i.e. information formerly in the reservoir's internal states - out of the computer system. This work is equal to or greater than the work that can be extracted by the Daemon.
Since the fate of the information handled by Maxwell Daemons has been well accounted for, particularly thanks to the work of Rolf Landauer and Charles Bennett, its status in physics is very different from the question of the fate of information contained in matter swallowed by black holes. My gut feeling is that most physicists in the field believe that here information is not destroyed either, but a full description of the information's fate will probably only be afforded by a full, working theory of quantum gravity, which we still do not have.
