I've had this incredibly frustrating experience as well. I've had times where it seems to take a couple of hours to come online. And when you are the one onsite trying to bring everything up - stressful.
The initial firmware upgrade is difficult to cope with as an IT person. So often I have seen engineers who are on site say it isn't working and power cycle/factory reset the MS - when in fact it was part way through the firmware upgrade process - and the result of their actions is that the whole process starts again - which to them re-affirms there is a problem.
These days before we deploy an MS we plug it in at our office at least 24 hours before we deploy it in the field. And we leave it there. No one touches it. If you aren't watching or waiting for it then no one is tempted to restart or mess with it.
If you can see two-way communication between the MS and the cloud and nothing is being blocked on the MX - try leaving it for a day. Make sure you can see successful DNS traffic, and that the two-way communication is actually exchanging data (and not just SYN packets and the like),
If you have already done a factory reset - raise a support ticket.