If your search requires UK hosts, and you happen to stumble upon Easyspace, leave the site and never look back!!!!!!! I was with them ages ago, and they had horrible downtime and the support was nonexistant. They are really cheap, but as always, you get what you pay for... DO NOT GO WITH EASYSPACE!!!!
Aside from that, I don't have any UK recommendations, but if you're on this side of the pond
Wantsomegetsome.net is good, they're my host now and I love it to death.
---Skorpion