This is the list of cloud hosting providers I know that offer their services from data centers located in the UK:
UK2.net (rebranded service from VPS.net)
vhhosts (iomart group)
Rackspace Cloud (formerly Mosso)
- Not really available in the UK, yet. "They are looking to make a physical presence in the UK sometime in early 2010".
Do you have some experience with any of them? Would you recommend some?