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.
Best Answer
I want to come back to this answer in a bit and expand a bit more, but it seems to me that the notion that you are reaching for is that of quasiparticles, and I want to argue that these might be best understood in the context of effective field theories.
Roughly: the electrons and holes in solid state physics are not actually necessarily true single particles, but actually collective excitations of the material (you can think of an electron quasiparticle as being an electron plus some minor deformation of the underlying lattice plus effects due to interactions with other electrons; the picture for holes is that of an empty electron quasiparticle state).
However, the same is true for electrons and positrons in vacuum (though the energy scales are much different)! The mass of the electron has contributions from a cloud of virtual electron-positron pairs (this is an effect called mass renormalization).
This is a bit confusing -- it turns out that e.g. talking about an electron as a single particle that doesn't interact with itself is a classical notion that breaks down when quantum field theory comes into the picture.
Indeed, quantum field theories (i.e. the best physical pictures that we currently have) are actually agnostic in a certain strong sense as to whether an electron is a single particle, or a particle surrounded by a cloud, or whether a hole is a true particle or a quasiparticle, etc. What do I mean by this? Well, the mathematical models that currently describe the systems best do not talk about particles at all, they talk about excitations in quantum fields, and for interacting quantum fields, it turns out that the coupling constants that go into the Lagrangians for these field theories will get (in general divergent!) corrections from self-interactions. Luckily, we now understand that this is not something to worry about -- there's a technique called "renormalization" which fixes the mathematical divergences, and there's a philosophy of "effective field theories" which explains how to think about these cancellations. Roughly speaking, depending on what energy scale you want to work in, you might interpret the electron as being a single particle, or a fuzzy cloud, but with regards to calculating measurable quantities, it doesn't really matter. For a better take on this, I like the first few sections of Howard Georgi's review "Effective field theory".
Sorry if this doesn't make much sense at the moment. I hope I've given you a few key words to look up. Perhaps someone who understands all this a bit better can come by and explain it in easier terms, or I'll come back and edit it in a few days.