Media Temple seems to have a good reputation and my boss is considering them as a new host.

But she asked me if the email situation would be stable and always up and running with them.

With our current web host, we have problems with our email -- important emails can't be sent/received or if they do, it would take days...sometimes it would go down. Not cool for a business to have an unreliable email server (as well as other issues with this host).

If you have personal experience with MT, let me know. Thanks.

Try to choose a web host who has backup email server ( Mx records actually ). ( Ask MT regarding the the same ;) )