When we had friends living in Mesa or nostalgic friends who had moved away, we would occasionally hit Los Dos Molinos on Alma School for New Mexico-style food. It has been several years since I've been there, but on my visits the food and margaritas hit the spot.
I've never tried to find proper Mexican food out that way.
Los Dos Molinos
260 S Alma School Rd Ste 137, Mesa, AZ 85210