The blackout and its schedule was created on a test system. Then it was exported using a custom cartridge and installed on the production system using this cartridge.
The cartridge contain also further customization, like dashboard, rules, etc... Each time a new customization came in or an existing one was changed a new version of the cartridge is being created.
When the cartridge will be installed on the production server, the blackout and its schedule will be overwritten, but the schedule contain the old starting date which is in the past. Therefore the first execution does not work, as it is in the past, but once the next execution is defined it is working fine again.
This happen with each installation of the custom cartridge and explained the random misfunction of the blackout.
Easiest way to solve this issue is to remove the blackout and its schedule from the custom cartridge. Add it only, if the blackout and/or schedule change.
Another option is to check the starting date of the blackout / schedule each time a new version of the cartridge has been installed.