Nice sleuthing.
This seems to be the crux of my issue as well. proxy.mobile.att.net resolves on my wifi network but all the requests time out. I'm not using pfsense or any firewall really so I'm not sure how to go about correcting this in my Netgear WNDR3700 router. I'll keep looking though.
My issue was that when I was connected behind my pfSense router and ran the ping, it wouldn't resolve at all. Once I tried the address from my work machine, proxy.mobile.att.net would resolve (172.26.39.1) but remain un-pingable. This is to be expected as the address is in a private address range that is unroutable across a public network.
If you're on your home network and your phone can ping and resolve but get no responses from the address above, then maybe you have a different problem. Try pinging the other addresses in your MMS APNs. Are you still using DD-WRT or are you using your ASUS router?
Sent from my Galaxy Nexus using Tapatalk 2