I think we've reached a point where most small companies can and should blindly use the cloud for everything that can be done remotely. There are only two situations where the cloud shouldn't be used:
1. If you're using tons of servers, you might benefit from hosting your own hardware on a large scale. But even then you can probably negotiate with the cloud service for a better price (like Netflix did). If you're a big customer and you think you should move off the cloud, the provider can beat your expected costs and still make a profit. Your team doesn't have thousands of years of combined hardware experience, and you're not buying hardware at a better price than Amazon got.
2) You don't want The NSA snooping on your company's data. This is a moot point because they will obtain the data anyway, with a gag order, if they really need to.
Why should a small company use the cloud for everything instead of a dedicated server or VPS?
Most small companies aren't going to benefit from the elasticity that the cloud provides. The administrative overhead will be similar on each except in the case of the cloud you need to worry about the persistence of data either via EBS, replication or having an acceptable loss level.
I would think remote dedicated servers and VPS services fall under the definition of "cloud"?
The question is whether or not you're paying up-front for hardware, and managing it locally somewhere. If you lease a $10/month VPS, you're using cloud services.
They don't access your servers "by default" on the cloud, because they have to go through Amazon, still spend effort, and it probably isn't as legal as obtaining things through a court order. But I think the chance is high enough that it's still worth considering hosting your servers locally.
1. If you're using tons of servers, you might benefit from hosting your own hardware on a large scale. But even then you can probably negotiate with the cloud service for a better price (like Netflix did). If you're a big customer and you think you should move off the cloud, the provider can beat your expected costs and still make a profit. Your team doesn't have thousands of years of combined hardware experience, and you're not buying hardware at a better price than Amazon got.
2) You don't want The NSA snooping on your company's data. This is a moot point because they will obtain the data anyway, with a gag order, if they really need to.