Teejnits, have you asked that one sub shop if they make their own mayo from scratch?
Mayo, from scratch, is nothing more than lots of oil, some raw egg yolk, a little vinegar, and some cayenne/Tabasco to cut the fatty flavor. Since the egg yolk is raw, it has to be handled carefully. This is where the "don't leave the mayo out (or in the sun)" bit comes from.
Commercially prepared mayo has stablizers and preservatives added to it, so it can withstand warmer temperatures better. Think about it, the stuff from the grocery store is CANNED AND STORED AT ROOM TEMP! Commercial mayo, in 1 gal tubs (or bigger), are also stored at room temp.
Talk to the manager, stating from the start that you have a quality-control and customer satisfaction issue. Be polite, and don't start or get involved in a raving screaming hissifit (I'm not saying you'd start one, but some managers have no sense). State your case. Ask if they use commercially-prepared mayo. Ask to see the ingredients of that product. Point out the stabilizers and preservatives. If they still won't budge, well, politely inform them that they have just lost your business, and that you're going to tell everyone that you know to avoid that place like the plague.