No relays need to be updated, and clients that want to adopt the new nip need to be updated. Your service can keep using kind 3, especially because it doesn't have to care about lists getting nuked because it only checks new entries.
Slight discrepancies between which lists have which entries is much better than catastrophic data loss. This NIP also allows clients that fail to fetch a user's list to add follows with confidence, and repair kind 3 when they're eventually found.