I really like your points and conjecture, though I disagree! So before getting to the point of the original question, I'd like to offer some comments and thoughts that can stimulate further independent thought.
Definition
Yours is a very good definition, and it is almost the exact definition we (the community) use for differentiating running from walking: any gait which includes phases in which all feet are completely off the ground is classified as a running gait.
This is however a category for several different gaits, including galloping but also trotting (there exist both running and walking trots), bounding, etc.).
As for galloping (and gaits in general) there are several different interpretations using different metrics (from order of foot-strikes to ground-reaction-force profiles), the usefulness of which depends a lot on what interests you. However I think the most widely accepted are the gait diagrams of Hildebrand, well explained in the wiki article. In this definition, the order and length of stance-phases is defining, and thus we have 2 separate types of gallop: a rotary gallop (seen in cheetahs and greyhounds, this involves 2 distinct flight-phases per cycle and is generally faster) and the transverse gallop (with only 1 flight phase per cycle, this is slower but more sustainable). Note that while several animals are able to use both, horses for example use the transverse gallop exclusively.
Points
- In the case of a quadruped the front pair of legs and the back pair of legs serve very different functions. [...]
This is true for many but not all morphologies (and for most we simply do not know). As an easy counter-example think of lizards and their sprawling postures (though elephants would also be a good example). Also, it depends not only on morphology but also gait.
In order to allow a fair comparison between two polypeds their masses must be equal and the available energy for mechanical work must be constant and equal for both.
This is a good point, but can (and should!) be circumvented through dimensionless analysis, see [1],[2] and [3] ([1] being imho the most readable). Essentially you need to compare dimensionless speed and time required for different things. Indeed, this sort of analysis is what imho would most strongly contradict your conjecture: you assume that hexapedal "scuttling" is slower than quadrupedal galloping, but I don't think it is! See [4] for a nice study on hexapedal running, and how this inspired robot design [5]. For the more casual reader, take a look at this TED Talk.
In order for a hexapod to gallop the middle pair of legs must be in phase with the front pair or the back pair. And in order to aid in propulsion they must be in phase with the back pair.
This statement seems quite heavily biased. A pseudo-quadrupedal morphology can also be achieved by a hexaped by simply lifting 2 legs! Also, considering the morphology as well as scale is extremely different, I would advise caution in applying assumption 4 (i.e. hind-limbs provide most power): in the quadrupeds we regularly think of (and of which the study you cite treats), mass and therefore gravity-effects are substantial. While hind-limbs are providing most propulsion, forelimbs are very important for providing vertical support! For most insects, gravity-effects can be largely ignored, so this division of roles may (and generally isn't) the same. Indeed think of lizards or other quadrupeds with a sprawling posture: they also do not exhibit the same type of division between hind and fore-limb.
You however point out a very insightful idea! By moving two (or more) legs in phase, you can approximate their effect as a single, virtual leg [6]! This has been a fundamental concept for a lot of early robotic work, as well as in quantifying and matching experimental data of animal locomotion to idealized models.
Why do different animals select different gaits?
This is the root of your original question and still very much an open question. The most substantial answer has been linked to energetics, by the Taylor & Hoyt study[7]: in this famous study, horses were trained to use specific gaits even when they preferred not to, and their oxygen consumption was the measured, in order to estimate the metabolic cost for each specific gait-speed combination. It was then found that horses would have a natural tendency to switch gait (if given the choice) at the speed where one gait became more efficient! You can test this out yourself on a treadmill. At certain speeds (usually around 8 km/h or so), you can still force yourself to walk (i.e. have no flight-phase) but it is actually more tiring and feels less natural than switching to a jog!
While this is quite convincing, there are other hypothesis. One which I myself subscribe to has a lot to do with the dynamic stability of a gait, i.e. the coupling between the mechanics and simple, low-level control. A nice result showcasing the viability of this explanation can be found here [8] (disclaimer, this is from my current lab).
If you'd like a bit more insight, or more math (this essentially starts going into non-linear dynamics from here on out, i.e. limit-cycles, basins of attraction etc.), or more references, please comment (I'm a bit hesitant, for fear of writing an unreadable wall of text...).
References
1: Vaughan, C. L., & O’Malley, M. J. (2005). Froude and the contribution of naval architecture to our understanding of bipedal locomotion. Gait & posture, 21(3), 350-362.
2: Alexander, R., & Jayes, A. S. (1983). A dynamic similarity hypothesis for the gaits of quadrupedal mammals. Journal of zoology, 201(1), 135-152.
3: Miller, B. D., & Clark, J. E. (2015, September). Dynamic similarity and scaling for the design of dynamical legged robots. In Intelligent Robots and Systems (IROS), 2015 IEEE/RSJ International Conference on (pp. 5719-5726). IEEE.
Chicago
4: Full, R. J., & Tu, M. S. (1991). Mechanics of a rapid running insect: two-, four-and six-legged locomotion. Journal of Experimental Biology, 156(1), 215-231.
5: Clark, J. E., Cham, J. G., Bailey, S. A., Froehlich, E. M., Nahata, P. K., Full, R. J., & Cutkosky, M. R. (2001). Biomimetic design and fabrication of a hexapedal running robot. In Robotics and Automation, 2001. Proceedings 2001 ICRA. IEEE International Conference on (Vol. 4, pp. 3643-3649). IEEE.
6: Raibert, Marc, Michael Chepponis, and H. B. J. R. Brown. "Running on four legs as though they were one." IEEE Journal on Robotics and Automation 2.2 (1986): 70-82.
7: Hoyt, D. F., & Taylor, C. R. (1981). Gait and the energetics of locomotion in horses. Nature.
8: Owaki, D., Kano, T., Nagasawa, K., Tero, A., & Ishiguro, A. (2013). Simple robot suggests physical interlimb communication is essential for quadruped walking. Journal of The Royal Society Interface, 10(78), 20120669.
9: Smolka, J., Byrne, M. J., Scholtz, C. H., & Dacke, M. (2013). A new galloping gait in an insect. Current Biology, 23(20), R913-R915.
original post:
I'm currently travelling so I will fill ou and complete my answer later. But as a teaser:
What is your definition for a gait and for galloping specifically? Generally we consider the order and duration (duty factor) each leg spends on the ground (i.e. in stance phase): these are depicted as gait diagrams, see Heglund et al or Alexander.
In this sense, a gallop is an asymmetric gait with flight phase (a phase when all feet are off the ground)... And who says hexapeds can't do it? ; ) indeed, though rare there have been observations of dung beetles galloping! They lift (iirc) their hindmost limbs off the ground completely and gallop with the rest. See [9].
As Orion says, a lot of changes in gait are due to low-level controls (i.e. Central pattern generators and reflexes) as well as mechanical properties od the morphology reacting to mechanical load, but this no reason primitive animals cannot have rich and adaptive gaits. As a counter-example, look up "decerebrate cat" on youtube: this famous experiment showed that indeed very basic low-level control can generate a rich variety of gaits in a cat, including the gallop!