Taking the lead from MrWizard, I did a little look for what the boys and girls in white lab-coats say.
In addition to the evidence presented at Snopes.com and the experts at the Ketchup Advisory Board (see MrWizard's answer) a few interesting articles (see below) all seem to point to this conclusion:
Commercially produced mayonnaise made with acetic acid is safe and due to its low pH, as well as the salt, and other additives it contains.
That, combined with the fact that none of the outdoor experts here have ever had mayo go bad on them... well, draw your own conclusions.
References (added emphasis mine):
Smittle, R.B. “Microbiological Safety of Mayonnaise, Salad Dressings, and Sauces Produced in the United States: A Review.” Journal of Food Protection 63, no. 8 (2000): 1144–1153.
The absence of reports of foodborne illness associated directly with the consumption of commercially prepared acidic dressings and sauces is evidence of their safety. Salmonella, E. coli O157: H7, E. coli, L. monocytogenes, Staphylococcus aureus, and Yersinia enterocolitica die when inoculated into mayonnaise and dressings.
and
The reported highest manufacturing target pH for dressings and sauces is 4.4, which is below the 4.75 pKa of acetic acid and below the reported inhibitory pH of 4.5 for foodborne pathogens in the presence of acetic acid.
Collins, M. A. “Effect of pH and Acidulant Type on the Survival of Some Food Poisoning Bacteria in Mayonnaise.” Microbiologie - Aliments - Nutrition 3, no. 3 (n.d.): 215–221.
All vegetative bacterial cells were eliminated in acetic acid mayonnaise pH <4.4. S. aureus was not eliminated from citric acid mayonnaise; in addition, at pH >5.0 both S. muenster and C. perfringens survived in this product.
Suggests that the type of acid is important (acetic better than citric) and PH is a factor (as noted in the first article). I believe all commercial mayo is still produced using acetic acid.
Weagant, Stephen D., James L. Bryant, and Don H. Bark. “Survival of Escherichia Coli O157:H7 in Mayonnaise and Mayonnaise-Based Sauces at Room and Refrigerated Temperatures.” Journal of Food Protection 57, no. 7 (1994): 629–631.
Escherichia coli O157:H7 strains, when inoculated and mixed into mayonnaise and stored at 25°C, became undetectable after 72 h storage when assayed by direct plating or by selective enrichment. The same strains inoculated into mayonnaise and stored at 7°C were detectable up to 35 days when assayed by direct plating or by selective enrichment.
Interestingly seems to suggest that at warmer temperatures, Mayo is more effective at killing E.Coli - likely (I imagine) to the general faster pace of biological processes at higher temps.