Information
I'll use my unlimited bytes how I see fit, thank you very much
Getting back to the topic at hand and adding value to the conversation, there are only a few ways to detect tethering, some of which require more effort on the part of AT&T than others.
TTL: In my opinion, the most likely telltale signal of tethering. iOS packets originate with a TTL of 64, so if they see anything else they know something is up. This is very easy to check, as the TTL is checked by each router as the packet is handled. (the address on the envelope - doesn't require opening the letter, to use an analog analogy)
APN: Another possible sign of tethering is data being routed over the access point set up for the built-in tethering feature. The makers of MyWi have allegedly said that they have always used the same APN that the built-in mail app, etc. use, so I don't know about this one. PDANet surely also uses the phone APN by now, if it didn't always. TetherMe at one point did use the other APN I believe, and there is a Cydia package to change it. Again, this is easy to check without deep packet inspection.
User-agent: This is where carriers would need to get heavy-duty equipment and a willingness to be invasive to detect tethering. Your browser sends information about itself to remote web servers, and this information could be checked. I do not think AT&T is doing this (to detect tethering at least,) as it is not proof of tethering since anyone can easily use another browser from the App Store that reports a different User Agent.
Web Sites Visited: Again, highly invasive, though it doesn't require DPI. If you're using the DNS servers of the carrier, they could look for requests for certain domain names like windowsupdate.com etc. This wouldn't be proof either, though.
I would bet that they are using TTL. I have only used Bluetooth tethering to my iPad since before they started doing this nonsense, and have never gotten a message, before changing my TTL, so tunneling the TCP/IP packets that way probably resets the TTL to the default of the WAN interface on the phone. Tethering only with an iPad isn't enough by itself - you need to tether an iPad (possibly more) using Bluetooth only in my experience.
I don't tether very much, though I do use a bunch of data on my unlimited iPhone plan. (I'll download a few massive Linux BluRay ISOs this month, just for you Spectrum

need to bring up the averages)
I've seen tons of people using under 2GB getting messages about tethering, so I think they want to get unlimited users off of those plans regardless.
As for whether PDANet will work, I've never tried it personally, but I've seen reports that people were left alone after turning on Level 2 masking. I don't know what PDANet does to mask it, but at the very least it changes the user agent.
You can manually change the TTL on a laptop or iPad to 65 as well, so packets originating from the cell modem will have the expected TTL of 64. Just google for it and I'm sure you'll find it. (iPad needs to be jailbroken to do this)
I need to put together directions on how to take a TCP/IP packet capture from the iPhone WAN interface so we can settle this matter once and for all.