Downtime tolerance certainly varies by application and there is a school of thought that proposes that applications with high availability requirements will never move to the Cloud.
"Independent Applications" that control all of its components should have no problems. Services like Amazon's EC2 provide so much flexibility and control that administrators and developers can feel right at home. Traditional recovery and redundant approaches can be put in place but with the benefit of having limitless (virtual) resources that can be launched on demand. These are the key ingredients to satisfy even the most demanding environments.
Applications that rely on external services face a bigger challenge. These applications will be as strong as their weakest link. Whether using public services or from partners these Mashups or composite applications will have to develop new patterns to handle exceptions and recovery. Maybe through data caching if timeliness requirements permit or maybe by re-routing to secondary providers. Whatever the approach might be, it seems that the first order of priority is working with IT leaders to ensure a smooth migration for the "Independent Applications".