The Stack Overflow podcast is back! Listen to an interview with our new CEO.
2 of 7 deleted 70 characters in body

You might use set operations: complement and union.

Assuming that recent notifications limited to 100.

Set<Id> updateNotifications(Set<Id> persisted, Set<Id> recent) {
    Set<Id> newNotifications = complement(recent, persisted);
    save(newNotifications);

    if (recent.size() < 100) {
        return union(persisted, newNotifications);
    }

    Set<Id> obsoleteNotifications = complement(persisted, recent);
    delete(obsoleteNotifications);

    return newNotifications;
}