Well, as a last resort, I set CID to T-MOB010 (stock for my phone), ran the latest RUU for T-mobile, and same result.
I've given it up for lost.

EDIT: HOLY F*CKBALLS.
So, I didn't give up after all. Found a couple of other threads, and apparently yes, you have to relock, reset CID, AND go S-ON (fastboot oem writesecureflag 3) and then run the RUU.
I have a stock fresh TMOUS 4.1.1 One S now.