rde_generate_updates is called with new and old (old_pathid_tx) to
identify the paths that were added or removed. I always get lost in what
combinations work or may show up. So lets have a look:

There are some limitations when it comes to new and old passed to
prefix_evaluate().
First of all, new->path_id_tx == old->path_id_tx unless new or old are
NULL. There is no way that a path is replaced with a different path.
Also in most cases if new != NULL then old == NULL and vice versa (but
there is also a case where both are set but then new != old).

For rde_generate_updates() the situation is similar. Either new is valid or
old is valid. If both are invalid then there is no need to call the
function. If both are valid only new matters (or better make old_pathid_tx
be 0).

prefix_evaluate_nexthop() behaves similar. If old was valid then new is
invalid but if old was invalid then new may still be invalid (because for
example the prefix may be filtered). Again if new is valid then there is
no need to pass old.

The diff below tries to put this into code. This should make it easier for
the next step which extends rde_generate_updates() to include a queue of
updates. It ensures that rde_generate_updates() is called only with these
options:
new != NULL, old_pathid_tx = 0
new == NULL, old_pathid_tx != 0

new == NULL, old_pathid_tx = 0 and new != NULL old_pathid_tx != 0 are both
invalid now. 
-- 
:wq Claudio

Index: rde_decide.c
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/rde_decide.c,v
diff -u -p -r1.106 rde_decide.c
--- rde_decide.c	1 Dec 2025 13:07:28 -0000	1.106
+++ rde_decide.c	19 May 2026 13:09:23 -0000
@@ -524,9 +524,11 @@ prefix_best(struct rib_entry *re)
 /*
  * Find the correct place to insert the prefix in the prefix list.
  * If the active prefix has changed we need to send an update also special
- * treatment is needed if 'rde evaluate all' is used on some peers.
- * To re-evaluate a prefix just call prefix_evaluate with old and new pointing
- * to the same prefix.
+ * treatment is needed if 'rde evaluate all' or add-path is used on some peers.
+ * To re-evaluate a prefix it is best to first call prefix_evaluate with
+ * new = NULL, old = prefix, adjust the prefix and then call prefix_evaluate
+ * with new = prefix, old = NULL. This ensures proper evaluation in case
+ * the prefix change influences prefix_eligible() or MED handling.
  */
 void
 prefix_evaluate(struct rib_entry *re, struct prefix *new, struct prefix *old)
@@ -552,8 +554,13 @@ prefix_evaluate(struct rib_entry *re, st
 		prefix_remove(old, re);
 		old_pathid_tx = old->path_id_tx;
 	}
-	if (new != NULL)
+	if (new != NULL) {
 		prefix_insert(new, NULL, re);
+		if (!prefix_eligible(new))
+			new = NULL;
+		else
+			old_pathid_tx = 0;
+	}
 	newbest = prefix_best(re);
 
 	/*
@@ -578,10 +585,10 @@ prefix_evaluate(struct rib_entry *re, st
 	 * rde_generate_updates() will then take care of distribution.
 	 */
 	if (rde_evaluate_all()) {
-		if (new != NULL && !prefix_eligible(new))
-			new = NULL;
-		if (new != NULL || old != NULL)
-			rde_generate_updates(re, new, old_pathid_tx, EVAL_ALL);
+		/* no old path to remove and path is ineligible, skip rest */
+		if (old_pathid_tx == 0 && new == NULL)
+			return;
+		rde_generate_updates(re, new, old_pathid_tx, EVAL_ALL);
 	}
 }
 
@@ -592,7 +599,7 @@ prefix_evaluate_nexthop(struct prefix *p
 	struct rib_entry *re = prefix_re(p);
 	struct prefix	*newbest, *oldbest, *new, *old;
 	struct rib	*rib;
-	uint32_t	 old_pathid_tx;
+	uint32_t	 old_pathid_tx = 0;
 
 	/* Skip non local-RIBs or RIBs that are flagged as noeval. */
 	rib = re_rib(re);
@@ -625,7 +632,8 @@ prefix_evaluate_nexthop(struct prefix *p
 
 	old = p;
 	prefix_remove(old, re);
-	old_pathid_tx = old->path_id_tx;
+	if (prefix_eligible(old))
+		old_pathid_tx = old->path_id_tx;
 
 	if (state == NEXTHOP_REACH)
 		p->nhflags |= NEXTHOP_VALID;
@@ -636,6 +644,15 @@ prefix_evaluate_nexthop(struct prefix *p
 	prefix_insert(new, NULL, re);
 	newbest = prefix_best(re);
 
+	if (!prefix_eligible(new))
+		new = NULL;
+	else
+		old_pathid_tx = 0;
+
+	/* path was and still is ineligible, skip rest */
+	if (old_pathid_tx == 0 && new == NULL)
+		return;
+
 	/*
 	 * If the active prefix changed or the active prefix was removed
 	 * and added again then generate an update.
@@ -657,9 +674,6 @@ prefix_evaluate_nexthop(struct prefix *p
 	 * to be passed on (not only a change of the best prefix).
 	 * rde_generate_updates() will then take care of distribution.
 	 */
-	if (rde_evaluate_all()) {
-		if (!prefix_eligible(new))
-			new = NULL;
+	if (rde_evaluate_all())
 		rde_generate_updates(re, new, old_pathid_tx, EVAL_ALL);
-	}
 }