In one embodiment, a switch in a computer network may receive a neighbor solicitation (NS) message for a target node for which no neighbor authentication (NA) reply has been received at the switch. The switch may then determine whether to forward the NS message to only non-constrained links of the switch, or to both non-constrained links and constrained links of the switch. The determining may be configured to intermittently result in forwarding the NS message for the target node to both the non-constrained links and the constrained links. The switch may then forward the NS message according to the determination.