In one embodiment, a packet switching device is configured to perform a lookup operation, based on a particular per-CE label (per-Customer Edge label) included in a particular packet, in a forwarding data structure for identifying forwarding information for the particular packet. When a corresponding outbound path is unavailable, a per-VRF (per-Virtual Routing and Forwarding) lookup operation in a VRF data structure, identified based on the particular per-CE label, based on a destination address of a packet encapsulated within the received packet. A corresponding packet is forwarded based on the results of the VRF lookup operation. In one embodiment, a set of more than one egress line card is identified based on this lookup operation, and packets of different routes are load balanced among egress line cards in this identified set of egress line cards.