I have no doubt that this may have been some crazy complicated case (as dealing with time can be) but I can't help the armchair quarterback debugging. Could this not have been addressed by periodically running a script that generated when (in UTC) a notification should be sent and then another script to send the notifications when that time comes around ie
Script 1: send notification to User 123 at 9:00 UTC
Script 2: It is 9:00 UTC, which users are due to have notifications that have not been sent?
This way, the timezones don't ever really come into play. The axiom I follow for dealing with time is collect and display time in user's local time but store and process in UTC.