Another alternative would be to have a separate package for the nssov overlay which would provide/conflict nslcd. That package (slapd-nssov?) could then also have the maintainer scripts configure and enable the overlay in slapd.
I don't think dropping the dependency is a good idea because users upgrading from older versions where the daemon was part of libnss-ldapd would end up with a non-functioning system without a clear way to fix it after an upgrade.
Another alternative would be to have a separate package for the nssov overlay which would provide/conflict nslcd. That package (slapd-nssov?) could then also have the maintainer scripts configure and enable the overlay in slapd.
I don't think dropping the dependency is a good idea because users upgrading from older versions where the daemon was part of libnss-ldapd would end up with a non-functioning system without a clear way to fix it after an upgrade.