@InfraBlue,
In NM, businesses are supposed to pay what is called a compensating tax on anything purchased out of state, whether it's internet or not. It's at the state rate and excluded county and city taxes. This is filed on the same monthly/semiannual report as gross receipts. I'm not sure if there is an individual requirement or not, and decline to comment on whether I've ever placed an internet order.