diff --git a/bgpd/bgp_advertise.c b/bgpd/bgp_advertise.c
index e0fa58d..be9b480 100644
--- a/bgpd/bgp_advertise.c
+++ b/bgpd/bgp_advertise.c
@@ -361,7 +361,7 @@
   XFREE (MTYPE_BGP_ADJ_IN, bai);
 }
 
-void
+int
 bgp_adj_in_unset (struct bgp_node *rn, struct peer *peer)
 {
   struct bgp_adj_in *adj;
@@ -371,10 +371,11 @@
       break;
 
   if (! adj)
-    return;
+    return 0;
 
   bgp_adj_in_remove (rn, adj);
   bgp_unlock_node (rn);
+  return 1;
 }
 
 void
diff --git a/bgpd/bgp_advertise.h b/bgpd/bgp_advertise.h
index 2cf2a29..adbbe30 100644
--- a/bgpd/bgp_advertise.h
+++ b/bgpd/bgp_advertise.h
@@ -133,7 +133,7 @@
 			struct bgp_node *);
 
 extern void bgp_adj_in_set (struct bgp_node *, struct peer *, struct attr *);
-extern void bgp_adj_in_unset (struct bgp_node *, struct peer *);
+extern int bgp_adj_in_unset (struct bgp_node *, struct peer *);
 extern void bgp_adj_in_remove (struct bgp_node *, struct bgp_adj_in *);
 
 extern struct bgp_advertise *
diff --git a/bgpd/bgp_route.c b/bgpd/bgp_route.c
index 34cb7c0..34ba1ab 100644
--- a/bgpd/bgp_route.c
+++ b/bgpd/bgp_route.c
@@ -2431,6 +2431,27 @@
 
   bgp = peer->bgp;
 
+  /* Lookup node. */
+  rn = bgp_afi_node_get (bgp->rib[afi][safi], afi, safi, p, prd);
+
+  /* Cisco IOS 12.4(24)T4 on session establishment sends withdraws for all
+   * routes that are filtered.  This tanks out Quagga RS pretty badly due to
+   * the iteration over all RS clients.
+   * Since we need to remove the entry from adj_in anyway, do that first and
+   * if there was no entry, we don't need to do anything more. */
+  if (CHECK_FLAG (peer->af_flags[afi][safi], PEER_FLAG_SOFT_RECONFIG)
+      && peer != bgp->peer_self)
+    if (!bgp_adj_in_unset (rn, peer))
+      {
+        if (BGP_DEBUG (update, UPDATE_IN))
+          zlog (peer->log, LOG_DEBUG, "%s withdrawing route %s/%d "
+                "not in adj-in", peer->host,
+                inet_ntop(p->family, &p->u.prefix, buf, SU_ADDRSTRLEN),
+                p->prefixlen);
+        bgp_unlock_node (rn);
+        return 0;
+      }
+
   /* Process the withdraw for each RS-client. */
   for (ALL_LIST_ELEMENTS (bgp->rsclient, node, nnode, rsclient))
     {
@@ -2445,15 +2466,6 @@
 	  inet_ntop(p->family, &p->u.prefix, buf, SU_ADDRSTRLEN),
 	  p->prefixlen);
 
-  /* Lookup node. */
-  rn = bgp_afi_node_get (bgp->rib[afi][safi], afi, safi, p, prd);
-
-  /* If peer is soft reconfiguration enabled.  Record input packet for
-     further calculation. */
-  if (CHECK_FLAG (peer->af_flags[afi][safi], PEER_FLAG_SOFT_RECONFIG)
-      && peer != bgp->peer_self)
-    bgp_adj_in_unset (rn, peer);
-
   /* Lookup withdrawn route. */
   for (ri = rn->info; ri; ri = ri->next)
     if (ri->peer == peer && ri->type == type && ri->sub_type == sub_type)