How can you ensure at least once notifications in a distributed system?

Lets say I have a calendar event:

calendar_event (
    id UUID,
    start_time timestamp,
    end_time timestamp, 
    ...
)

And I let users create notifications for those events

notification (
     id UUID, 
     event_id UUID, # the id of the event in calendar_event
     notification_time timestamp, # the time the notification should be sent
     notification_sent boolean DEFAULT false, # true if the notification has been sent
)

And this app is used enough that I have multiple nodes (restful java applications for example) processing create events, create notifications, and delete notifications etc. and storing that data in some database, e.g. MySQL.

And lets also assume that it is critical that I send the notification on time, and users are able to update notifications in the very near future.

How can I ensure that each notification is sent at least once?

---

We could have another app that is polling every minute, and then sending the notifications, but if that app is down for any length of time we will have missed notifications. If we mark notifications as sent using the boolean field, then we could catch up, but we could be late. And if we're storing the next minute, and a notification is deleted, and should therefore not be sent, we will send a notification when we should not.

I am reminded of a queue, but with some different properties; we need to sort by notification_time, not insert time, and we need to allow deletes.