Office 365 no update notification

I would suggest to have a look at the log files at C:\Windows\Temp, these should tell you the root cause. Look for log files which are a bit larger and search for "TryLoadScenario - Loading UPDATE scenario is successful" which indicates an attempt to discover new updates. Continue reading the lines, especially the very long ones. You should be able to figure out why the update discovery doesn't work from there.