Original AT&T iPhone exclusivity was a 5 year deal
As long-speculated, the original iPhone exclusivity agreement between Apple and AT&T was for a 5-year period running from 2007 to 2012. Confirmation of this comes by way of court documents from 2008, however, and 2 years is an eternity in corporate contract-dom.
In other words, anything from AT&T's service levels (or lack thereof in New York and San Francisco) to their deal for iPad 3G data plans could have led to renegotiations, extensions, or new contracts entirely since then.
So file this away under iPhone trivia unless and until a Verizon iPhone shows up... sometime.