Personally I think Microsoft proved 365 within 4-5 years of 365 hitting the market. Let's see...I think it came to market in 2006...and we got invited to a sneak preview of the partner program (granted..stinky margins back then, before CSP came out). But...by 2010 we had quite a few clients moved from SBS to O365..mostly E3 then.
Going back to RackSpace, before 2010, it was still viable, although, by 2007, if someone needed to move from on prem Exchange, or get real email and grow up from POP/IMAP, we brought them to 365.
Before 2006, we had a few clients on RackSpace's hosted Exchange. And they DID have a cool "hybrid bundle"...which was rare. Have the big wigs on hosted Exchange, and have the general troops on lowly (aka cheap) IMAP mailboxes.
While RackSpace used to be a big grand daddy of hosted services....web, mail, DNS, virtual servers, and good old Jungle Disk, there was one company that really made the name of hosted Exchange prior to them, Intermedia!
But back to RackSpace, I'm guessing they didn't have Datto Siris for backup, else they'd have been back up by dinnertime last Thursday!