I'm absolutely not an attorney, and this is not qualified legal advice. That said, I don't think the world is as easy as Bhargav and NetTecture's comments above indicate.
First, of course it is legal to host a server overseas. Obviously.
The finer point is which legislation you are subject to, when it comes to stuff like customer's privacy, email advertisements/spam, personally identifiable information (especially credit card information), and taxation (sales taxes a.k.a. VAT in particular).
I'm a citizen of the EU. I'm pretty sure I could argue in court over here that you are subject to the EU's data privacy laws when doing business with me. After all I am a EU citizen, and the server that physically stores my data is also inside the EU. If you're a US company with a server on US ground, then I would have a harder time arguing that EU's data privacy laws apply, and the Safe Harbor Principles would seem a better fit.
Is this something to worry about? I a decade in the business I have not heard of a startup getting into trouble over which jurisdiction its servers are hosted in. I would not worry about this; instead I would invest in sound principles on data handling. I.e. have good Terms of Service, don't store credit card information yourself but offload that to a 3rd party, and don't ever spam or resell email addresses. Regarding taxation -- it's a huge topic, one that I will not try to answer.
To your questions:
Do I have to register my business in the UK as well?
What I have seen so far is: Almost all smaller US companies don't create subsidiary companies in the EU at first. Then when they grow 'large', they create subsidiaries over here -- f.x Amazon, Paypal and others have subsidiaries. If you get lots of sales in EU, you might need to register a company here to better serve your customers, or to comply with EU VAT laws. But not just because a virtual server is here.
What happens with things like Akamai and distributed hosting - where your website and/or copies of it could be moving around the world dynamically?
Honestly, I don't think the laws have caught up with technology on this one. But in most cases, what Akamai would cache globally is less important stuff such as website CSS or images. The important information, such as personally identifiable information, is usually not spread around the globe but resides in a single (or max 2) datacenter(s).