BT Cellnet -> O2
Started on PayG, then went on contract direct with O2 about 4 years ago now. I initially went with them because I live out in the sticks, and we had the choice between O2 (you got full signal as they had a big mast 100 yards down the road), or Vodafone (my father's work mobile was vodafone, and the only place he could get signal then was outside; so the number of times he'd spend a half hour sat in the car on the drive, on a work call was quite funny!)
Now, i'm still with O2 as i've got a good retention deal, plus their signal's always top notch wherever I go. Most of my mates are with them, so my unlimited o2 to o2 calls come in handy! Never had any billing horror stories either, so no reason to leave. I'd be telling a different story if I needed mobile data, as I'll agree that o2's offerings here are pretty poor... plus if you do need speed, their 3G network does leave a lot to be desired. However, as it is, my main use is voice calls and texting, with the occasional MMS, so i've just switched 3G off to save power for now. I guess i'd take out a seperate 3 contract if I needed mobile data!