I use positive-internet, to be honest they are a bit pricey, but the only hosting company who promised not to delete any pop3 emails no matter how old they were (1+1 had something daft like 1mth, but please dont take my word on that)
Another thing I like about positive is their attitude, email them and within a couple of hours you've got a non-standard responce email, chatty, but efficient and knowledgeable.
http://www.positive-internet.com/zhosting.html
They hosted the record breaking podcast from Ricky Gervais too as mentioned on the homepage
http://www.positive-internet.co.uk/