Notification not working for some devices

We have a group of 5 devices and library which defines notifications for a certain sensor (Syslog receiver) on every of these devices. While this notification works fine for some devices, it completely fails for others. On the devices where notification fails, the log shows that the sensor in question goes into error state properly, but without a notification being triggered. The notification setting coming from the library is show in the notification settings dialog as expected. The error states last long enough to trigger a notification, as they actually do on other devices being served by the same notification library. How can this happen?