Unlimited Storage
Solution 1:
Most services that say they are offering unlimited web space, mail space etc., aren't. They are relying on the fact that 99% of people using it will never get anywhere near that, its called overselling and its quite prevelant in cheap webhosts, i'm usually dubious of anyone offering unlimited space, particularly small hosts who would obviously not have the infrastructure to deal with it.
If you were actually going to offer unlimited space then you would need some sort of system that allowed you to expand drive space as and when required, dynamicaly, like some sort of SAN or NAS and the systems to support it.
Solution 2:
It's pretty simple, they claim it's unlimited, and hope that they won't run out of disk space quicker than they can get more.
You can make this kind of gamble with or without virtualisation ;)
Solution 3:
When it comes to email, it depends on the system. Exchange, for instance, can scale very far by its self. When coupled with an integrated Archiving solution that uses its own separate databases for the older stuff, expansion can be done quite simply. The end user just sees one huge mailbox, even though their data exists in both the Exchange mail-stores, as well as the Archive databases. Newer technologies are beginning to introduce de-duplication into the process for further storage efficiencies.
The hard part comes when you convert from a system with a quota to one without a quota, as that's when your users will transition from self-policing to stay under quota to 'keep everything just in case'. Past growth curves will be broken beyond all recognition. Once all the users are used to the idea that they won't be yelled at for keeping their entire lives in their mailboxes (and they will) the growth curves become more useful for planning future hardware purchases. At that point, it really is just staying ahead of the growth curve with hardware.