"There is also the question of how good a job they do with encrypting the data."
Most let you manage your own keys. So as long as you have a reasonable key management, it's up to YOU, not the provider.
"Are there regular security audits by an outside party who can affirm that the things the cloud company claims are in fact accurate?"
For the big players, yes. http://aws.amazon.com/complian.... Also "AWS has achieved ISO 27001 certification and has been validated as a Level 1 service provider under the Payment Card Industry (PCI) Data Security Standard (DSS). We undergo annual SOC 1 audits and have been successfully evaluated at the Moderate level for Federal government systems as well as DIACAP Level 2 for DoD systems."
Every one of those compliances requires auditing.
"What happens when an employee leaves the company? How is access controlled to prevent continued access?"
You federate your enterprise IAM with your cloud provider. Most support some form of SAML or OAuth. ADFS (an MS product) supports such things easily. You terminate the employee in your normal system and their IAM account is terminated. Also, you don't give deep credentials to most people but rather wrap them in services. You then stash those credentials in a secret/key server.
"To me, cloud is all smoke and mirrors."
That is because you haven't done the required reading.