Hmmmm... This is all rather compelling. If moving back to the States won't get me out of a certain provider's contract then I won't be able to consider them an option. I will look at Unitymedia's site / call them about contract cancellation.
See, the thing with O2 is that I've heard nothing but bad things about it, also from people outside of this forum. Although, if they have no minimum contract or at least, would let me cancel when I move, they may be my best bet. Also 30 a month, that's really good, as long as it works.
@Soulreaver: Nice avatar. I don't think you could get any closer to crossing over the NSFW line.