I'm not doubting what you just said about your experience but I updated 2 iPhone 4S yesterday that are no longer tied to any service. I updated both iPhones without any trouble. Sorry to hear about yours
My old ones have been this way for a long time. Any old sim will work, then take it out after "activation". Just remember to cycle messaging and face time off then back on to disassociate them with the phone number on the old SIM card.