I use Newnet and although they charge for connection and stuff I've never been unable to connect in 16 months.
They also show what your usage is on an hourly basis which is useful...
EDIT oh and it's a 2mb line (although they do do 8) and I pay £12 a month but that's with a 3GB of usage - then it's a fiver for every 5GB after that or something.
I was on a 20GB usage for £20 a month but I found I rarely used more than 3...
EDIT 2
www.newnet.co.uk