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.