I'd say linode, I've had great experience with them, you get your own machine, so you can stack it however you want, pricing is reasonable, service and documentation is great. Heres a link to uk based servers: http://www.linode.com/avail/
Little is known of the specifics in the Bitcoin-related Linode security incident. This was all that was released: http://status.linode.com/2012/03/manager-security-incident.h...