I'm not a security expert, but at least I have first hand experience with the Bitcoinica hack. It seems that all the security features you have mentioned are present in many Bitcoin sites, including Bitcoinica,r and they don't prevent the easiest ways of losing wallets.
Storing in the cloud is especially dangerous because for most (NOT all) cloud service providers, the front-end security (concerning authentication and authorization) is probably much weaker than your own implementation. For example, anyone can reset the password with an email, and change the root passwords of the servers. There isn't likely an option for second factor authentication.
This does not apply to cloud services with serious security considerations, such as AWS. It has IAM as well as second factor authentication. However, in Bitcoinica's case, both Linode and Rackspace don't seem to be a good choice to host wallets: Linode hack was actually a result of their customer service system compromise (i.e. possibly any support agent can reset the root passwords). While Rackspace Cloud's support staff couldn't log out the hacker and preserve the servers even when the hack was detected and password being changed.
These are really basic security features that cloud services are lacking.
You made a good point that things can be upgraded as you grow. Please do that. It's exactly what I intended to do when I launched Bitcoinica last year. But after I sold the company last year, no one really think it's an urgent thing to do because there were no performance issues, no availability issues and everything went just fine. It's important to stick to the plan, and preferably allocate a fixed portion of revenue for upgrading security features and doing audits.
I'm glad to give you more information so that you can make better decisions (just drop me an email). I have been leading Bitcoinica for half a year (until the handover in April) and I had some experience in running a Bitcoin site that scaled quite well. I'm working on a non-Bitcoin project at the moment but I really want Bitcoin to succeed.