Buenas...
A mí también me pasa esto mismo. Tengo todo actualizado, y estoy conectado a WiFi o a 4G indistintamente cuando me salta esta notificación.
En efecto, fue a raíz de la actualización grande de más de 4 GB con los parches de enero de 2019 de Google. En mi caso, el móvil lleva la compilación oficial 9.1.0.310, con el software personalizado de Orange, sin rootear, y fue de los últimos en actualizarse.
Además, como información extra, puedo aportar que esta notificación me salta algunas veces, no siempre, pero todas las veces que lo hace es siempre cuando lo conecto a la corriente para que cargue.
Como solución temporal, acudo a la aplicación "Configuración de Android", le desmarco la opción "Permitir notificaciones" y así se va, volviendo a marcar luego la opción, pero entiendo que esto no es una solución definitiva, pues preferiría dejar a dicha aplicación de sistema las notificaciones activadas, por si me avisa de algo importante.
A ver si hay suerte y se puede aportar una solución que no sea la de restaurar de fábrica el teléfono.
Saludos.