Funnily enough, having looked through the recent updates, one of these updates (KB3114409) was actually supposed to "adds administrative support to prevent Outlook 2010 from booting into safe mode. Administrators set this function in some scenarios when
they have add-ins that must be enabled"
They have now updated this with the following notice:
"After you install this update, Outlook 2010 may start only in safe mode. If this issue occurs, uninstall the update. This update is no longer available now."
I will be uninstalling this now.
Just uninstalled update KB3114409, rebooted my laptop, and Outlook is back to normal now.