A Telco blocking features of a phone, any features is like stealing from you. I buy an LG or Samsung for the features listed on the box or website and if I found a feature to be missing the box and phone will be promptly returned and I'd demand my money back, and contract canceled! It's just an unthinkable thing for a Telco to do.
I understand and agree with the outrage you feel, but the status quo is powerful and slow to change. There are telcos that explicitly provide tethering in their plans as a standard feature, and bringing an outside device to operate with the telco is easier than it used to be, so maybe things are starting to shift.
They act like you need a whitelisted IMEI, but the network doesn't actually care. The tricky part is getting a SIM activated on their network.
The store managers pretend like they can't give/sell just a SIM. They're supposed to give them to you for free, but lie to sell you a handset. You can buy them from resellers who DGAF. They also pretend you need a whitelisted IMEI to activate the SIM card, their website and in-store people enforce this rule. I've always had good luck calling their 1-800 number and playing dumb. At the very worst you can probably find an old or broken verizon phone for free/cheap and use that IMEI.
$500 early termination fee, 8-12 weeks for a "partial refund" via cheque ;)