A first network device is configured to originate an actual route by sending a multicast join message to a particular next-hop network device, and in conjunction with originating the actual route, to generate an empty route associated with the next-hop network device for use in limiting a number of withdrawal messages that would otherwise result upon a failure in the actual route. The first network device may be further configured to generate an unreachability indicator message for the empty route indicating that the next-hop network device is unreachable responsive to the failure in the actual route, and to send the unreachability indicator message for the empty route to one or more additional network devices, with the unreachability indicator message causing each such additional network device to delete multiple actual routes to the next-hop network device that are represented by the empty route.