I think that you confused yourself with many things.  First of all, nobody needs a US visa to go to Canada.  If you are H-1B, you DO need a Canadian visa.  And if your I-94 is valid, you can simply return to the US with your I-94.
As for New Mexico, when did it leave the United States of America?  What I am saying is that New Mexico is one of the 50 states in the US, not another country.  If you are going to Mexico, the same rules (as for Canada) apply.