Carphone Warehouse, in January. £49 up front, and £25 a month for 2 years, for 500 texts, 600 mins (or is it 900?) and unlimited internet. Not gone over any of my limits yet, and I hammered it in the first month.
That was the cheapest deal for me. It was £30 a month in store, £25 online...
At £500 new for a phone, I reckon I am only paying £150 for a 2 year unlimited internet contract, which I can also run my laptop through via tethering