That is pretty incredible. I knew about ISP's DNS servers that hijacked NXDOMAIN but I've never before heard of MITMing of third party DNS servers! Wow! Have you contacted T-Mobile about it?
I haven't, but that's a good idea. I'm guessing there are semi-legitimate reasons beyond just forcing people to the stupid NXDOMAIN search page. But I agree that it's pretty unpleasant.