My current internet provider is Be Internet. They're not super-cheap, but they're not insanely expensive either. I've been with them for nearly four years now, and they're bloody brilliant. This endorsement does not come with any kickbacks from them, although if you are persuaded then I'll be happy to formally introduce you.
The reason I raise this is because they've been in the tiny minority of people who, while moving house over the last month, have promised and then delivered. They gave me a date for connection, they connected me on that date, they sent me an email saying I was working, I plugged in my modem and I had a connection. Hallelujah.