Didn't look at Windows Azure as an option? http://www.microsoft.com/windowsazure/
1) It's expensive compared to other hosting platforms. 2) I hate lock-in to a particular platform. If we coded against Azure tables we would be locked in to Azure. If we used their SQL platform we would be space constrained. 3) I have used Azure and deployment, updates, and troubleshooting are all slow and cumbersome. It is still a very immature platform.
We've found that like for like the Azure platform is very well priced and is actually less expensive than our current Ubuntu setup, as well as being cheaper than comparable high level Microsoft hosting providers.
We don't much like lock in either and for the parts of the Azure platform that will lock us in we're extracting the code into a wrapper so we can replace with the minimum of work should we need to switch hosting platform in a hurry. Database wise we're going with SQL Azure and their 10GB limit I find to be quite spacious for our needs, although that would depend entirely on what you're storing. I believe they have 50GB databases in the works for the near future?
The deployment times are an issue and I have heard similar, but again I believe if you upload the project yourself then request the update the deployment time is greatly reduced making it less of an issue. It would take some doing to match Capistrano deployment though which is simply awesome and something I will certainly miss.
I actually used a powershell script to automate deployments on Azure, it was the delay from when you do that which is so frustrating. Waiting 5-10 minutes was fairly normal.