1dbase vs. many and cloud hosting vs. dedicated server(s)?

Me and my partner are making a blueprint for an online webshop service. The purpose of this project is to make webshops available for small company's/ individuals automatically just by creating an account with us. Our webapp can be used to add products/pages/... to the store and we'll handle secure checkout by paypal.

Our app should be scalable and manageable. Because we also want to offer free webshops, the amount of webshops could be +10.000 within a few years. We are building on the Zend framework and are using mysql for database.

From the start we want to build our application for optimal and easy scalability in the future, to avoid a lot changes to our app/database in the future.

Now our questions are:

Should we use?:
* one database for all shops (or limited to X shops );
* one database for each new shop (each having products, orders... tables);

I think both approaches have PRO/CONS. What do you think ? Does anyone has experience with this kind of structure ?

PRO:
one database: easier to make changes to database layout
multiple databases:more scalable, easier to backup/restore

CON:
one database: harder to code because of extra keyfields in tables , slower or more difficult to backup/restore.
multiple databases: Takes longer to push changes to database layout

We are totally not clear on what hosting we should use. Would it be a solution to use a cloud service such as mosso/amazon/gogrid? Or is it better to just start with one dedicated server and expand 'manually' later?

Thanks in advance for your help!