I think that the cloud is the way to go, because you can scale up and down your infrastructure as needed. But, presuming that the problem is indeed the database, you'll have to re-architect the database.
SQL doesn't scale easily, unless you spend a bunch of bucks for an Oracle Enterprise server. However, a NoSQL database would be easily scalable to multiple nodes, and you can add them or subtract them as necessary to meet peaks and valleys in demand.
Aside from the implementation effort, there's the cost. Amazon's EC2 cloud can do everything you want, and more -- but at a price.
Yes, my former boss David C. mentioned this as well. There are pros and cons to this approach as well. One major one, to my mind, is there is no ACID for NoSQL (atomicity, consistency, isolation, durability). There's also little standardization in API's or Query Languages for NoSQL. Therefore, I conclude that it is an immature -- albiet promising -- technology.
SQL doesn't necessarily scale, but there are methods of writing code so that it scales a lot better:
On the SQL side itself: