Turns out this was caused by @DawPis DP45) Mod Action Notify Enabled 2.0.5.1 plugin which was creating custom notifications which were associated with the core application. So once the plugin was disabled, the 3rd party notifications were still loaded because they were associated to the core application but the parse method was missing because of the disabled plugin.
We're going to catch the error on the frontend, but this will also result in a guideline change, any future submissions which need own notification types will have to be a proper application with an own notification extension.