Well, well, well... we has this discussion here; in Brazil, some years ago when the GSM begun to work.
All this happens because is very easy change the Simcards between cellphones.
So, we solved this here with some simple solutions:
=> The carrier can sell phones with subsidy (for example, IPhone 5 for $ 500.00 + expensive contract) or without subsidy (IPhone 5 for $ 1,300.00 + no contract);
=> The carrier cannot refuse to sell the devices, with or without subsidy;
=> The carrier cannot "hide" the devices to sell only with subsidy: if I want a Galaxy SIII and the store have only one, I can buy subsidized or not;
=> All devices; subsidized or not, can be sold locked, but the carriers MUST unlock, if the client ask for;
=> The customer (and not the device) is bind to contract, and not by devices;
=> If I want to buy some Galaxy Note II subsidized, I can ask for unlock without problems;
=> If I don't pay my bills, the carrier can add my ID number (CPF in Brazil, SSN in USA) in our black list credit system (I don't know if there is something like that in USA or Canadá) and block the phone number, but never the device.;
=> The device is added in carrier's black list ("bad imei", like "bad esn") only if the device was lost or stolen, and registered the fact in police.