How can the Hall effect ever show positive charge carriers?

There are two essential facts that make a hole a hole: Fact (1) The valence band is almost full of electrons (unlike the conduction band which is almost empty); Fact (2) The dispersion relation near the valence band maximum curves in the opposite direction to a normal electron or a conduction-band electron. Fact (2) is often omitted in simplistic explanations, but it's crucial, so I'll elaborate.

STEP 1: Dispersion relation determines how electrons respond to forces (via the concept of effective mass)

EXPLANATION: A dispersion relation is the relationship between wavevector (k-vector) and energy in a band, part of the band structure. Remember, in quantum mechanics, the electrons are waves, and energy is the wave frequency. A localized electron is a wavepacket, and the motion of an electron is given by the formula for the group velocity of a wave. An electric field affects an electron by gradually shifting all the wavevectors in the wavepacket, and the electron moves because its wave group velocity changes. Again, the way an electron responds to forces is entirely determined by its dispersion relation. A free electron has the dispersion relation $E=\frac{\hbar^2k^2}{2m}$, where m is the (real) electron mass. In the conduction band, the dispersion relation is $E=\frac{\hbar^2k^2}{2m^*}$ ($m^*$ is the "effective mass"), so the electron responds to forces as if it had the mass $m^*$.

STEP 2: Electrons near the top of the valence band behave like they have negative mass.

EXPLANATION: The dispersion relation near the top of the valence band is $E=\frac{\hbar^2k^2}{2m^*}$ with negative effective mass. So electrons near the top of the valence band behave like they have negative mass. When a force pulls the electrons to the right, these electrons actually move left!! I want to emphasize again that this is solely due to Fact (2) above, not Fact (1). If you could somehow empty out the valence band and just put one electron near the valence band maximum (an unstable situation of course), this electron would really move the "wrong way" in response to forces.

STEP 3: What is a hole, and why does it carry positive charge?

EXPLANATION: Here we're finally invoking Fact (1). A hole is a state without an electron in an otherwise-almost-full valence band. Since a full valence band doesn't do anything (can't carry current), we can calculate currents by starting with a full valence band and subtracting the motion of the electrons that would be in the hole state if it wasn't a hole. Subtracting the current from a negative charge moving is the same as adding the current from a positive charge moving on the same path.

STEP 4: A hole near the top of the valence band move the same way as an electron near the top of the valence band would move.

EXPLANATION: This is blindingly obvious from the definition of a hole. But many people deny it anyway, with the "parking lot example". In a parking lot, it is true, when a car moves right, an empty space moves left. But electrons are not in a parking lot. A better analogy is a bubble underwater in a river: The bubble moves the same direction as the water, not opposite.

STEP 5: Put it all together. From Steps 2 and 4, a hole responds to electromagnetic forces in the exact opposite direction that a normal electron would. But wait, that's the same response as it would have if it were a normal particle with positive charge. Also, from Step 3, a hole in fact carries a positive charge. So to sum up, holes (A) carry a positive charge, and (B) respond to electric and magnetic fields as if they have a positive charge. That explains why we can completely treat them as real mobile positive charges in their response to both electric and magnetic fields. So it's no surprise that the Hall effect can show the signs of mobile positive charges.