We did resolve this, but have also signed up for Google Apps and will be migrating next year. I ended up having to roll all office installations back by about 6 months (Version
1705 (Build 8201.2102)).
I had to push Group Policy to disable Windows Updates and change to the Semi Annual channel, rather than Semi Annual Targeted channel. I will try re-enabling updates in a few months in the hope that the issue has been mysteriously addressed.
We were using Office 365 Pro Plus and Excel 2016, and ended up trying both Version 1711 (Build 8730.2127) and Version 1708 (Build 8431.2131), same issue in both. I believe the issue was introduced in builds prior to this though, some time around the start
of September or thereabouts. There was no resolution for those recent versions for us. It wasn't waiting for input as per Mike Ansell's suggestion (but thanks anyway for the suggestion), it was just a buggy build.
Roll back procedure:
https://support.microsoft.com/en-us/help/2770432/how-to-revert-to-an-earlier-version-of-office-2013-or-office-2016-clic
Versions & Channels:
https://support.office.com/en-us/article/Version-and-build-numbers-of-update-channel-releases-ae942449-1fca-4484-898b-a933ea23def7
I hope the above can help anyone in similar situation, it became a crippling problem for our business as more and more PC's got patched with the buggy build.