STAB physical water is an excellent attacking type. I generally find it a lot easier to sweep with DDgyara then I do with DDmence.
Gyarados is generally bulkier (only 1 base stat advantage in defense for salamence, but bullet punch resist is far more valuable, and gyarados is specially bulkier then dragonite).
Looking at the top pokemon in OU:
Scizor-Gyarados does far better then mence (although mence can use fire attacks), in that gyara can set up on scizor (while mence is forced to try and kill imediately), and can only be revenge killed by scizor when at very low health.
Salamence- Mence is mence. When either comes in on the other they get an intimidate; if one switches in on the other as the other DDances, the one with the dragon dance wins one on one (due to being faster, and having a super effereffective attack). However, as it is the faster one that wins, this would mean salamence would typically be the 1 on 1 winner (being faster).
Heatran- Often carry hp ice/dragon pulse, which means that gyarados can set up more easily. Gyarados has to be jolly to outspeed scarftran after a DD, however. Gyara can also avoid running eq and still hit it for super effective, as one note.
Gyara-same comments as for mence.
Infernape- Often carries HP ice, something mence has a far harder time trying to survive then gyara does the occasional stone edge.
Metagross- gyara does resist steel, and could therefore switch in more easily, although offensive metagross does tend to carry t-punch (LO meteor mash OHKOs mence after stealth rock, however).
Tyranitar- Gyara's STAB is super effective, so it would have a better claim at holding a lead then mence does.
Blissey- blisseys do occasionally carry ice beam (although thunderbolt is something I saw on suspect a few times as well). Mence could hit it harder.
Swampert- carries ice beam, and can even survive +1 LO outrage. HP: electric is far rarer.
Latias- Outspeeds and can OHKO either of them.
Lucario- mence is probably a little better here, being actually able to outspeed lucario. Both are often used to "counter" luke, however.
Gengar- OHKOed and outsped by either after set up (unless it has scarf). Thunderbolt>gyara if gar is faster.
Jirachi- being a steel type, it can come in on outraging mences.
Zapdos- being an electric type, gyara obviously has more to fear, but 'dos being sr week would need to make sure it roosts regularly to stay at high health, as otherwise it could only come in a few times (though, gyara would suffer the same problem). Mence obviously does better against zapdos, but a t-bolt can threaten a good bit of damage.
Celebi- walls gyara. DDmence also doesn't enjoy celebi very much at all (but celebi would need t-wave to be able to solidly end mence, as grass knot doesn't accomplish much). 11.4% of gyara do have bounce, however, so depending on the team gyarados can be geared to overcome.
Starmie- threatens gyarados more.
Azelf- not much of a difference, although if it is a special attacker, gyara would take less damage.
Breloom- salamence does much better here of course (though, neither want to switch into a spore).
Gliscor- gyara hits it with a super effective stab.
Vaporeon- gains health when switching into gyara's stab, and 37% have hp electric (while only 30% have ice beam) so it's clear that gyara is far more threatened.
Bronzong- resists mence's stab, but nuetral to gyara's.
Skarmory- same as above. If skarmory doesn't promptly whirlwind, it is playing with fire as it is bound to get flinched by waterfall (or meet a crit) and then die after being unable to roost.
Going on much further then this probably wont help make the point get across any better.
I think I actually got very carried away and didn't realize I'd better stop typing. I went on autopilot for a little while because I'm getting tired...
The point I was trying to make-and hopefully got across without explicitly stating above-is that they are different pokemon, and fair differently when facing different threats (and can also each be adapted towards being better able to overcome different threats, such as adding bounce to gyara). Depending on the team DDgyara can very often be a better fit then DDmence (or, as you mentioned yourself, when the team already has a different version of mence, such as mixmence).
Also, Gyarados has 81 base speed, not 80. The 1 base stat point difference there in speed has some impact.
EDIT:
My biggest disagreement is over the "much better STAB" comment. Looking at the top 30, their are 8 dragon resists, and 8 water resists. An exactly equal number of resists for both of their STABs.
I'd say, from that selection, gyara's STAB actually looks better (but it depends on the team which you personally care to hit hard, and which you don't).
Doing the math to see the total number of dragon resist usage among OU pokemon and total number of water resist usage reveals:
Dragon resist: 631309
Water resist: 606199
I'd be more then happy if someone were to double check whether or not I missed anything when adding these pokemon up (again, it is late).
That is more dragon resists then water resists. That makes water the better attacking type here.
There is also a kicker in that physically bulky pokemon (excluding bulky waters), which are generally ground and steel types, are week or nuetral to water. Contrast this to DDmence who is often instead forced to use STAB outrage, so that the physically bulky resist can come in and then simply dispatch mence.
Many of those water resists are from sweepers (the two most used water resists are salamence and gyarados, both of whom are week to stone edge...although I'm surprised to see that is only ran 54% of the time), while most bulky things are only neutral (all the steels barring the relatively rare empoleon; and the ground types such as hippo and gliscor are week to it).
Mence having "much better STAB" is a comment that is simply wrong.