I got it solved!! I got help from an official Samsung Representative via Samsung Experience Store that's built into a nearby Best Buy. This seems to be their version of the Apple Genius Bar.
After Kies3 didn't work I decided to contact Samsung. I live-chatted with them and the end result was, rather quickly, that the best course of action would be to have an official rep give flashing a try with something they call Samsung Smart Tool. I went to a Best Buy and the nice lady gave it a try. It took a few goes and about an hour, but in the end she was able to restore my device to stock (KitKat, so upgraded stock I guess since my phone came with Jellybean).
First she tried some automatic recovery, which failed.
Second she tried to have her system recognize my device, which also failed. She said that might be the device being too borked to work, but it could also just be that not every Samsung handset is in their auto-recognition system. The backup plan was easy; she went to a site and downloaded a stock image given the model number printed on the phone. I believe she used SamMobile
Third, she tried a flash of M919UVUFNB4_M919TMBFNB4_TMB.zip using Samsung Smart Tool while my phone was in fastboot, but the flash only got to 1%.
She thought the 1% might be something incompatible about that ROM so she downloaded M919UVUEMK2_M919TMBEMK2_TMB.zip and gave that a try, but only got to 10%.
Finally she went back and tried the first package again, this time it worked.
Note: After the successful flash the phone clearly would not boot all the way the first time. It got to the Tmobile logo and stuck therefor about 5 minutes before she restarted, at while point we saw some "android is updating X of Y apps" message, the booting completed after about 5 minutes, and the device is back to working and unencrypted!!