Josh -
You might consider looking at the example of NOP running on Windows Azure someone shared here:
https://www.nopcommerce.com/boards/t/1502/nopcommerce-running-on-azure.aspxAzure in theory should make on-demand availability of NOPCommerce possible, and support a heavier user base for the money.
Azure still might be over-kill for most implementations of NOP given the possible scalability of most of the current hosting solutions available, however, I still think it's worth a thought if performance and scaling to larger customer (shopper) bases without compromising performance are part of your concerns.
If your worried about professional look and feel, templating and UI isn't anything your traditional web-design shop with some ASP background couldn't handle.
Also, having some experience with Cloud-computing I think nopCommerce will be the first open-source solution that could be actively installed with a complete feature set into an on-demand environment. Salesforce.com has some scalable eCommerce Apps via it's "AppExchange", but I don't know how customizable they are or open-source. Also, same customization problems without scalable solutions offered via eBay or Amazon.
Just my 2-cents.
What concerns did you have specifically? I'm consulting a company about that size right now, and will most likely be moving them to a new platform after the Christmas season, but multi-store is very important to them, so I'm gathering my thoughts about what direction to go.