If a hosting company wants to offer hosted exchange services as a product offering it can be done.
I will not go into the details of the infrastructure however in short mission critical so it should be robust high performing and sustainable against failures.
In short create lots of OUs (organizational units) name each one based on the client companies name. within that OU you can create the users who are members of that client company as well as distribution lists. If you want one of the users to create mailboxes on their own just delegate rights to that OU.
On the exchange side create storage groups, you can start with more SGs however depending how many clients you start to put on it, it may get out of hand. The idea behind multiple SGs is to not share the I/O resources and also improve the backup and recovery process should disaster strike.
Last but not least you will want to read up on GALs and OABs, create security groups in each OU per client and grant that group rights to that GAL/OAB and all others deny, this way they wont share resources or view their existance.
A lot of fine tuning in between, best of luck!