Microsoft is doubling the size of mailboxes of Exchange Online and Office 365. Small business mailboxes have now 50GB of storage size. The Office 365 blog has a table of all new mailbox sizes.
I am using Exchange Online for a year or so and I am a heavy mail user, but I didn’t even get close to the 25GB even though I never delete an email. Nevertheless, 50GB of storage for this price (€3.30 per mailbox) is amazing.
Many cloud offers are quite expensive which is often justified because of the flexibility they offer. Office 365 is an exception. It is inexpensive and flexible.