I don't think office 365 was too late to the party. If they did it any earlier they would have had more problems than they did anyway (and they had quiet a bit of problems early on).
Heck the place I'm going through the interview/background process with has had licenses for all employees for office 365 for about 1.5 years. But, It just takes so much time to move everyone they are only at about 20% of people on office 365 now. They have 3 exchange servers on site. and over 20TB of mailboxes. (Don't remember exactly how many thousands of users) But, yeah it take people plenty of time to migrate.
And if you have a lot of employees that don't need full on exchange, I'm thinking places where only managers get exchange but normal employee don't last long. Then Rackspace has a better deal for hybrid system with their email and exchange.