I'd suggest two hosting options for a server

www.34sp.com - based in Manchester, and are pretty darned good. In fact, one of my old workmates works there, and he's pretty good at what he does! Co-lo there is around 90 pounds per month, but it's pretty good, and you get an excellent plesk control panel. I use them myself - but use the reseller hosting plan, which is good for my needs at 15 pounds per month.

www.1and1.co.uk - they do a co-lo server from 29.99 per month (with 10Gb of transfer per month).

Either way, qmail is set up on both, ready to go.

Hope this helps!
cheers,
Luke