What's the difference between a VPS and “cloud hosting”?
Not much. That's because there's no industry-standard definition of “cloud hosting”. As a result, many “cloud” providers simply re-label their VPSes as “cloud servers”. A VPS gives you scalable resources on demand, easy system backups and OS reloads, a virtualized operating environment, and backup nodes in the event of hardware failure.
Some cloud providers offer advanced features like redundant SAN storage or geographically-distributed servers. These providers typically charge a substantial price premium over a VPS. In addition, because not all servers are created equal, you may not get the same performance that you'd get with a VPS -- some cloud providers still base their performance levels on CPUs from 2007!
It's important to examine your needs and determine whether or not you'll actually benefit from the additional costs associated with true cloud hosting.