The map on the Mexicana website is a bit out of date, I think. It doesn't show Denver at all, but they do fly there.
(a) Veracruz is top of my list for places to visit.
(b) Frontier is teaming up with the Mexican Tourist Authority for a big push on the Mexican routes. I'd guess they'd tell F9
what routes they they can sell the best.
It seems clear that Frontier regards Mexico as fertile ground. What isn't clear is whether they see it as a "one way street". Obviously they're taking US tourists to Mexico. It would be interesting to know how much traffic they think they can pick up from Mexico.