What happens when a "matter-black-hole" and an "anti-matter-black-hole" collide? Let's say we have one black hole that formed through the collapse of hydrogen gas and another that formed through the collapse of anti-hydrogen gas. What happens when they collide? Do they (1) coalesce into a single black hole or do they (2) "annihilate" into radiation?
One would expect (1) to be the case if the No Hair Theorem were to hold. So I guess what I'm really asking for is a modern understanding of this theorem and its applicability given what we know today.
 A: I suspect there is a bit of a difficulty here.  A particle $p$ and its anti-particle $\bar p$ cancel each other, and if they have a mass $m$ this results in the production of massless bosons (photons). Quantum number which identify the particle $p$ are subtracted away by opposite quantum numbers of $\bar p$.  These quantum numbers usually are the lepton or baryon numbers, electric charge, isospin and so forth.  However, anti-matter does not have anti-mass.
Dirac’s original idea was that the Klein-Gordon equation had a square-root according to spinors.  If the particle has a mass there are then two roots for the momentum, which define a surface in $\pm$ portions of the momentum light cone.  The negative portion of the cone defines the so called Dirac sea, where the mass of particles is negative.  All of these negative energy (mass) states are however completely filled up.  This is why this is called a “sea,” for they define a ground state which has no dynamics.  However, if you impart a package of energy to a state in the sea so its energy flips sign you can generate an anti-particle with positive mass-energy.  However, all the other quantum numbers are reversed, including the charge.
One could then construct a black hole from a huge cloud of hydrogen and anti-hydrogen of equal mass.  Based on the final state of the black hole it is not possible to determine whether it was formed by hydrogen or anti-hydrogen.  So if you have two such black holes, one from $H$ and the other from $\bar H$ the two will coalesce into a larger black hole.
The Schwarzschild solution in its pure form has a past and future singularity, where the past singularity corresponds to a “white hole.”  The white hole is about the closest thing there is to an “anti-black hole.”  These do not exist in nature, or at least have not been identified astronomically.  They may play some role in the very early universe, but nature is such that there is an asymmetry (asymmetry in their occurrence etc) between the black hole and white hole.  However, the white hole does not have an “anti-mass.”
A: And now an experimentalist chimes in:
Baryon number conservation depends on the lifetime of the proton at low energies, admittedly quite large but finite in many theories. 
At high energies, high enough for a quark gluon plasma to form, the preponderance of baryons becomes a slight excess of quarks versus antiquarks in the soup. This because quark antiquark pairs continuously form and annihilate in the sea, and if one would want to keep a conserved number that would be the excess number of quarks over antiquarks in a matter plasma and vice verso in an antimatter one.
One supposes that in the collapse of a hole the energies are sufficient for a quark gluon plasma to form and thus make moot the point of baryon number and antibaryon number assumed in the question. The excess of quarks in one hole versus the excess of antiquarks in the other would be proportionately very diluted to assume that the hole could be characterized as matter or antimatter anyway, even if all  other valid  physics arguments already presented by others were not present.
A: They simply merge to be a bigger hole. There is no matter outside of the horizon so they will merge without incident. Nothing that happens inside the hole will affect the outside, so we can't see any annihilation reactions.
