Every year as WWDC approaches, the Apple rumor mill spins up and starts suggesting that the iPhone will be announced for additional carriers in the US.

The obvious carrier in question is Verizon. Just as large as AT&T, Big Red’s 3G coverage and voice quality far surpass AT&T is many regions. In fact, the most recent rumor — just out this morning — claims that Verizon is testing iPads on their network.

Verizon would benefit immensely from an iPhone, without a doubt. The number of AT&T customers who stay with the carrier just for Apple’s handset has to be staggering. People are ready for a change, and Verizon’s reputation — and service to back it up — keeps some AT&T customers with their eyes on the door.

As an additional perk for Apple, Verizon’s focus (and customers) would likely shift away from RIM and Android handsets. Right now, the Droid and Droid Incredible are the best phones Verizon sells. I’d bet that would change if there was an iPhone display in the stores.

The immediate red flag is that Verizon uses CDMA phones that are incompatibly with GSM networks used by AT&T and most carriers around the world. An AT&T iPhone isn’t different internally than one sold at O2 or another overseas company. Apple would have to build a different device just for Verizon.

While that may not be a big issue if Apple can sell enough CDMA handsets, it’s worth thinking about.

If they were to offer the iPhone, Big Red could find its network overwhelmed with data, just like AT&T has. Verizon prides itself on the robust nature of its network, but iPhone users consume much more data than other smartphone owners.

It is doubtful that any carrier would have done better than AT&T did when the iPhone first arrived. My issue with AT&T is that network upgrades have been very slow to take shape.

All of this discussion about iPhone exclusivity has just been speculation for a long time. However, AT&T has recently made some policy changes that seem to indicate they are afraid of losing iPhone customers.

First, on May 22, AT&T announced the cancellation fee for the iPhone would be doubling to a total of $325, reduced $10/month until contract is completed. While this isn’t outrageous (Verizon charges $350), it is twice what the company used to charge. A high termination fee often is enough for people to stick with their current carrier for the length of their contract.

The other shoe dropped this morning when AT&T announced a overhaul of their data plans for the iPhone and iPad. The changes are a mixed bag. They are removing the “unlimited” plan for future customers — capping data at 2GB/month. Additionally, they are flipping the switch on iPhone tethering for $20/month, which coupled with that data cap, isn’t ideal.

Why not charge $30/month and allow tethering and unlimited data? In my opinion, those data caps seems to be a compromise AT&T designed to protect its network, which is already fragile.

It’s clear that something is happening at AT&T. The data changes go into effect June 7 — the day of Steve Jobs’ keynote at WWDC. Why pre-announce it? Bigger yet, not let Steve announce it last night at D8?

Someone mentioned to me this morning that AT&T may be trying to save face after Jobs cut off a question about tethering the iPhone at D8 last night. I don’t see that being a big enough reason to pre-announce something that was scheduled to be unveiled at WWDC, less than a week away.

AT&T hasn’t changed much about the iPhone plan since 2007, so two major changes in two weeks is weird. Considering WWDC is just around the corner, AT&T may have gotten spooked about the iPhone’s exclusivity. They have a lot to lose if someone else offers the iPhone. Do I think that I’ll be able to buy an iPhone and put it on my Verizon plan later this summer? I’m not sure. By gut says no, but my my brain is starting to think yes.