The phrase that really needs to be dusted off in these cases is "punitive damages".
Fines that amount to simply replaying what has been deceitfully taken are just not enough as they are no deterrent at all.
Any time these companies are found out and made to pay up, they come out more-or-less even but when they get away with it, they win. This happens in other areas too, like banks and their various charges and penalties and insurance companies not paying out or paying out fractions of what they should.
Simply paying/repaying what they should is not a penalty and thus not a deterrent.
It's like saying that if someones is found guilty of stealing a car, their 'punishment' is to return the car or pay for it. That's ridiculous, clearly!
Now, what AT&T have done is not criminal so you can't go sending them to jail, but you still need to punish them so that the punishment acts as a deterrent to others and this is precisely where punitive damages come in.
The very purpose of such damages is to fine the company sufficiently so that it cannot be seen as a cost of doing business and thus actually acts as a deterrent.