There was an interesting Economist article [0] a few years back that suggested a better option might be "penalties that offset the benefits of crime" rather than ones that try to arbitrarily 'punish' the offender. You'd see much larger fines, but they wouldn't be so large as to cause additional, unexpected consequences. The tricky part is improving detection rates, which increases the risk of the action even setting aside the question of fine size.
Compared to cartel price-fixing, Verizon's UIDH insertion is actually much easier to detect. In fact, anyone can do so just by looking at their access logs. I think that, more than fine size, will be the primary reason that they won't try this again. That's not to say they won't play other games, however.
Anyhow, if you really want to change a particular behavior, class action suits offer a much more attractive option where they're possible. They don't really benefit the class members financially (they're not supposed to), but they are one hell of a big stick. And historically, a very effective one at that. Even when companies prevail, they tend to take notice and often change the behavior in question.
0. http://www.economist.com/node/21559315