Sounds like the your host mail server is down.
UB has 4 mail servers, when one goes down there is outages for particular users on that mail server. Seems like Google would use the same kind of Idea for their millions of Users. You are probably just on a problematic server. Its kind of weird, I would think they would have a pretty reliable backup. Unless there are multiple outages and/or scheduled outages