5 of 7 added 80 characters in body

Using complement operation from set theory. And assuming recent notifications limited to 100.

Set<Notification> updateNotifications(Set<Notification> persisted, Set<Notification> recent) {
    Set<Notification> newNotifications = complement(recent, persisted);
    save(newNotifications);
    persisted = persisted.addAll(newNotifications);

    if (persisted.size() <= 100) {
        return persisted;
    }

    Set<Notification> obsoleteNotifications = complement(persisted, recent);
    delete(obsoleteNotifications);
    persisted = persisted.removeAll(obsoleteNotifications);

    return persisted;
}

class Notification {
    /* Fields provided by service */
    boolean dismissed;
}

Notification class presumably deserialized from JSON and dismissed set to false by default. After each service fetch call updateNotifications to save new notification and delete old, if necessary. Already persisted notification don't rewritten during an update. So flags in persisted notifications preserved.