I recently migrated my email from a small Exchange hosting provider that is having some growing pains to Office 365. Rather than choosing one of the small business plans, I chose the Office 365 Midsize Business plan for $15/mo per user.
Quick note: In a later article, I'll discuss why I chose Office 365 over, for example, Google Apps.
With only two users (my wife and me), we are far from a midsize business, but the level of complexity of what I do often puts my projects into the enterprise category when it comes to the level of problem-solving required.
I chose the Midsize Business plan over the Small Business Premium (also $15/mo) because a Microsoft representative told me that the Midsize Business support team was part of Enterprise support and was more equipped for handling complex problems.