diff --git a/CHANGES.rst b/CHANGES.rst
index 2016d604ed9fb014a708f24fe7e2a8e0b304e4ca..2494e5c2d1fe7984d4927f1969e2c73a5284c2ec 100644
--- a/CHANGES.rst
+++ b/CHANGES.rst
@@ -62,11 +62,12 @@ Node
   ``plugin.removed_fees_too_low_for_mempool`` have been replaced with
   ``node.mempool.rejected_by_full_mempool`` and
   ``node.mempool.removed_from_full_mempool`` with different
-  descriptions and messages. In particular, the
-  ``rejected_by_full_mempool`` error no longer indicates the minimal
-  fee needed by the rejected operation to be accepted by the full
-  mempool (however, we are working on providing this information
-  again). (MR :gl:`!6787`)
+  descriptions and messages. The ``rejected_by_full_mempool`` error
+  still indicates the minimal fee that the operation would need to be
+  accepted by the full mempool, provided that such a fee exists. If
+  not, the error now states that the operation cannot be included no
+  matter its fee (e.g. if it is a non-manager operation). (MRs
+  :gl:`!6787`, :gl:`!8640`)
 
 - RPC ``/helpers/forge/operations`` can now take JSON formatted operations with
   ``attestation``, ``preattestation``, ``double_attestation_evidence`` and
diff --git a/src/lib_shell/prevalidation.ml b/src/lib_shell/prevalidation.ml
index 49a45e7f8da94b9b7e1ca94eb982d9a84d36e76b..dc083748512baeea5acf9eb2be1425bd13f7b9bd 100644
--- a/src/lib_shell/prevalidation.ml
+++ b/src/lib_shell/prevalidation.ml
@@ -220,6 +220,21 @@ module MakeAbstract
         return_some (removed, `Outdated trace)
     | Unchanged -> error [Operation_conflict {new_hash = op.hash}]
 
+  let bounding_add_operation bounding_state bounding_config op =
+    Result.map_error
+      (fun op_to_overtake ->
+        let needed_fee_in_mutez =
+          Option.bind op_to_overtake (fun op_to_overtake ->
+              Filter.Mempool.fee_needed_to_overtake
+                ~op_to_overtake:op_to_overtake.protocol
+                ~candidate_op:op.protocol)
+        in
+        [
+          Validation_errors.Rejected_by_full_mempool
+            {hash = op.hash; needed_fee_in_mutez};
+        ])
+      (Bounding.add_operation bounding_state bounding_config op)
+
   (* Analyze the output of [Proto.Mempool.add_operation] to handle a
      potential operation conflict. Then use the [Bounding] module to
      ensure that the mempool remains bounded.
@@ -243,9 +258,7 @@ module MakeAbstract
       | Some (replaced, _) -> Bounding.remove_operation bounding_state replaced
     in
     let* bounding_state, removed_by_bounding =
-      Option.to_result
-        ~none:[Validation_errors.Rejected_by_full_mempool op.hash]
-        (Bounding.add_operation bounding_state bounding_config op)
+      bounding_add_operation bounding_state bounding_config op
     in
     let mempool =
       List.fold_left Proto.Mempool.remove_operation mempool removed_by_bounding
diff --git a/src/lib_shell/prevalidator_bounding.ml b/src/lib_shell/prevalidator_bounding.ml
index 9e7a90e453f0b9084ebfa4d8e07d29067c45bca3..681edf63a8c1064dec9a795df43bcc18f41cd707 100644
--- a/src/lib_shell/prevalidator_bounding.ml
+++ b/src/lib_shell/prevalidator_bounding.ml
@@ -58,7 +58,7 @@ module type T = sig
     state ->
     config ->
     protocol_operation operation ->
-    (state * Operation_hash.t list) option
+    (state * Operation_hash.t list, protocol_operation operation option) result
 
   val remove_operation : state -> Operation_hash.t -> state
 end
@@ -181,10 +181,31 @@ module Make (Proto : Tezos_protocol_environment.PROTOCOL) :
     in
     aux state []
 
+  (* Remove the minimal operation until there is room for [op], and
+     return the last operation removed this way.
+
+     Precondition: the [state] satisfies the invariants but does not
+     already have room for [op].
+
+     We don't need to check the [config.max_operations] bound because
+     removing one operation is always enough to add [op] without
+     breaking it.
+
+     Note that this can only return [None] when removing all
+     operations is still not enough to make room for [op] -- ie., when
+     [op.size > config.max_total_bytes]. *)
+  let rec find_op_to_overtake config state op =
+    match state.minop with
+    | None -> None
+    | Some minop ->
+        if state.total_bytes - minop.size + op.size <= config.max_total_bytes
+        then Some minop
+        else find_op_to_overtake config (remove_present state minop) op
+
   (* Precondition: [op] is valid (otherwise calling
      [Proto.compare_operations] on it may return an error). *)
   let add_operation state config op =
-    if Operation_hash.Map.mem op.hash state.ophmap then Some (state, [])
+    if Operation_hash.Map.mem op.hash state.ophmap then Ok (state, [])
     else
       let state =
         {
@@ -203,9 +224,15 @@ module Make (Proto : Tezos_protocol_environment.PROTOCOL) :
       if List.mem ~equal:Operation_hash.equal op.hash removed then
         (* If the new operation needs to be immediately removed in
            order to maintain the mempool bound invariants, then it
-           should actually be rejected. *)
-        None
-      else Some (state, removed)
+           should actually be rejected.
+
+           We feed to [find_op_to_overtake] the [state] returned by
+           [enforce_bound_invariants] to avoid handling again the
+           operations removed by it: we already know that removing
+           them is not enough to make room for [op]. *)
+        let op_to_overtake = find_op_to_overtake config state op in
+        Error op_to_overtake
+      else Ok (state, removed)
 end
 
 module Internal_for_tests = struct
diff --git a/src/lib_shell/prevalidator_bounding.mli b/src/lib_shell/prevalidator_bounding.mli
index 883b0b3979b4d73555110a6cf819b157eac904c2..bbd1d30ac36b34ff37ceb9855cf96396e3fa24d5 100644
--- a/src/lib_shell/prevalidator_bounding.mli
+++ b/src/lib_shell/prevalidator_bounding.mli
@@ -77,17 +77,25 @@ module type T = sig
 
   (** Try and add an operation to the state.
 
-      When the mempool is not full (i.e. adding the operation does not
+      When the state is not full (i.e. adding the operation does not
       break the {!max_operations} nor the {!max_total_bytes} limits),
       return the updated state and an empty list.
 
-      When the mempool is full, return either:
+      When the state is full, return either:
       - an updated state and a list of replaced operations, which are
         all smaller than the new operation (according to the protocol's
         [compare_operations] function) and have been removed from the
         state to make room for the new operation, or
-      - [None] when it is not possible to make room for the new
+      - an [Error] when it is not possible to make room for the new
         operation by removing only operations that are smaller than it.
+        In that case, the error contains [op_to_overtake], that is, the
+        smallest operation such that if the new operation were greater
+        than [op_to_overtake] according to [compare_operations] (but
+        with an unchanged byte size), then it could be successfully
+        added to the state. The [Error] can only contain [None] when
+        no matter how the new operation compares to others, it can
+        never be added, ie. the new operation has a bigger size than
+        {!config.max_total_bytes} by itself.
 
       When the operation is already present in the state, do nothing
       i.e. return the unchanged state and an empty replacement list.
@@ -99,7 +107,9 @@ module type T = sig
     state ->
     config ->
     protocol_operation Shell_operation.operation ->
-    (state * Operation_hash.t list) option
+    ( state * Operation_hash.t list,
+      protocol_operation Shell_operation.operation option )
+    result
 
   (** Remove the operation from the state.
 
diff --git a/src/lib_shell/test/test_prevalidation.ml b/src/lib_shell/test/test_prevalidation.ml
index 2778c1cc0c76756d4a346e039a3281336455ad9f..9d341078b880e9661d75483b4f80dc3b886a224d 100644
--- a/src/lib_shell/test/test_prevalidation.ml
+++ b/src/lib_shell/test/test_prevalidation.ml
@@ -426,13 +426,15 @@ type bounding_outcome =
           than [n]).
           In practice we generate [0 <= n <= 3], and very often [n = 0]
           meaning that there is no replacement. *)
-  | B_none  (** Return [None]. *)
+  | B_error
+      (** Return [Error op_to_overtake_opt] where [op_to_overtake_opt] is
+          randomly [None] or an operation present in the state. *)
   | B_crash  (** Raise an exception. *)
 
 (** This generator returns:
     - with odds 3/5: [B_success 0]
     - with odds 1/15 each: [B_success n], for [1 <= n <= 3]
-    - with odds 2/15: [B_none]
+    - with odds 2/15: [B_error]
     - with odds 1/15: [B_crash]
 
     We strongly favor [B_success 0] (aka add the operation without any
@@ -444,7 +446,7 @@ let bounding_outcome_gen =
       ( 12,
         let* n = frequencyl [(9, 0); (1, 1); (1, 2); (1, 3)] in
         return (B_success n) );
-      (2, pure B_none);
+      (2, pure B_error);
       (1, pure B_crash);
     ]
 
@@ -462,41 +464,50 @@ let bounding_outcome_gen =
 module Toy_bounding :
   Prevalidator_bounding.T
     with type protocol_operation = Toy_proto.operation
-     and type state = Operation_hash.Set.t * bounding_outcome = struct
-  type state = Operation_hash.Set.t * bounding_outcome
+     and type state =
+      Toy_proto.operation Shell_operation.operation Operation_hash.Map.t
+      * bounding_outcome = struct
+  type protocol_operation = Toy_proto.operation
+
+  type state =
+    Toy_proto.operation Shell_operation.operation Operation_hash.Map.t
+    * bounding_outcome
 
   (* Similarly to [Toy_proto.Mempool.t], we initialize the [state]
      with the outcome [B_success 0] so that it is easy to add
      operations to the mempool and make it grow. *)
-  let empty = (Operation_hash.Set.empty, B_success 0)
-
-  type protocol_operation = Toy_proto.operation
+  let empty = (Operation_hash.Map.empty, B_success 0)
 
-  (** Remove and return [n] random elements from [set].
-      If [n > cardinal set], then return all the elements of [set] instead.
+  (** Remove and return [n] random hashes from [ophmap].
+      If [n > cardinal ophmap], return all the keys of [ophmap] instead.
       Not tail-rec because in practice it is used with n <= 3. *)
-  let rec pop_n set n =
-    if n <= 0 || Operation_hash.Set.is_empty set then (set, [])
+  let rec pop_n ophmap n =
+    if n <= 0 || Operation_hash.Map.is_empty ophmap then (ophmap, [])
     else
-      let oph =
-        QCheck2.Gen.(generate1 (oneofl (Operation_hash.Set.elements set)))
-      in
-      let set = Operation_hash.Set.remove oph set in
-      let set, popped = pop_n set (n - 1) in
-      (set, oph :: popped)
+      let oph = random_oph_from_map ophmap in
+      let ophmap = Operation_hash.Map.remove oph ophmap in
+      let ophmap, popped = pop_n ophmap (n - 1) in
+      (ophmap, oph :: popped)
 
-  let add_operation (set, desired_outcome) _config {Shell_operation.hash; _} =
+  let add_operation (ophmap, desired_outcome) _config op =
     match desired_outcome with
     | B_success n ->
-        let set, replaced = pop_n set n in
-        let set = Operation_hash.Set.add hash set in
-        Some ((set, desired_outcome), replaced)
-    | B_none -> None
+        let ophmap, replaced = pop_n ophmap n in
+        let ophmap = Operation_hash.Map.add op.Shell_operation.hash op ophmap in
+        Ok ((ophmap, desired_outcome), replaced)
+    | B_error ->
+        let op_to_overtake =
+          let open QCheck2.Gen in
+          if Operation_hash.Map.is_empty ophmap || generate1 bool then None
+          else
+            Some (snd (generate1 (oneofl (Operation_hash.Map.bindings ophmap))))
+        in
+        Error op_to_overtake
     | B_crash -> assert false
 
-  let remove_operation ((set, outcome) as state) oph =
-    if Operation_hash.Set.mem oph set then
-      (Operation_hash.Set.remove oph set, outcome)
+  let remove_operation ((ophmap, outcome) as state) oph =
+    if Operation_hash.Map.mem oph ophmap then
+      (Operation_hash.Map.remove oph ophmap, outcome)
     else state
 end
 
@@ -520,12 +531,12 @@ let () =
   let open P.Internal_for_tests in
   let add_op state (op, (proto_outcome, bounding_outcome)) =
     let proto_ophmap_before = get_mempool_operations state in
-    let bounding_ophset_before = fst (get_bounding_state state) in
+    let bounding_ophmap_before = fst (get_bounding_state state) in
     assert (not (Operation_hash.Map.mem op.hash proto_ophmap_before)) ;
-    assert (not (Operation_hash.Set.mem op.hash bounding_ophset_before)) ;
+    assert (not (Operation_hash.Map.mem op.hash bounding_ophmap_before)) ;
     let state = set_mempool state (proto_ophmap_before, proto_outcome) in
     let state =
-      set_bounding_state state (bounding_ophset_before, bounding_outcome)
+      set_bounding_state state (bounding_ophmap_before, bounding_outcome)
     in
     let*! state, returned_op, classification, replacements =
       P.add_operation state P.default_config op
@@ -533,7 +544,7 @@ let () =
     (* Check the classification. *)
     (match (proto_outcome, bounding_outcome) with
     | Proto_success _, B_success _ -> assert_success ~__LOC__ classification
-    | Proto_success _, B_none ->
+    | Proto_success _, B_error ->
         assert_rejected_by_full_mempool ~__LOC__ classification
     | Proto_unchanged, _ -> assert_operation_conflict ~__LOC__ classification
     | Proto_branch_delayed, _ ->
@@ -545,19 +556,19 @@ let () =
         assert_exn ~__LOC__ classification) ;
     (* Check that the states have been correctly updated. *)
     let proto_ophmap = get_mempool_operations state in
-    let bounding_ophset = fst (get_bounding_state state) in
+    let bounding_ophmap = fst (get_bounding_state state) in
     let count_before = Operation_hash.Map.cardinal proto_ophmap_before in
     let count = Operation_hash.Map.cardinal proto_ophmap in
     (match (proto_outcome, bounding_outcome) with
     | Proto_success proto_replacement, B_success nb_replaced_bounding ->
         assert (Operation_hash.Map.mem op.hash proto_ophmap) ;
-        assert (Operation_hash.Set.mem op.hash bounding_ophset) ;
+        assert (Operation_hash.Map.mem op.hash bounding_ophmap) ;
         List.iter
           (fun (replaced, replacement_classification) ->
             assert (Operation_hash.Map.mem replaced proto_ophmap_before) ;
-            assert (Operation_hash.Set.mem replaced bounding_ophset_before) ;
+            assert (Operation_hash.Map.mem replaced bounding_ophmap_before) ;
             assert (not (Operation_hash.Map.mem replaced proto_ophmap)) ;
-            assert (not (Operation_hash.Set.mem replaced bounding_ophset)) ;
+            assert (not (Operation_hash.Map.mem replaced bounding_ophmap)) ;
             assert_replacement ~__LOC__ replacement_classification)
           replacements ;
         let nb_replaced_proto =
@@ -569,7 +580,7 @@ let () =
         assert (count = count_before + 1 - nb_replaced)
     | _ ->
         assert (not (Operation_hash.Map.mem op.hash proto_ophmap)) ;
-        assert (not (Operation_hash.Set.mem op.hash bounding_ophset)) ;
+        assert (not (Operation_hash.Map.mem op.hash bounding_ophmap)) ;
         assert (List.is_empty replacements) ;
         assert (count = count_before)) ;
     (* Check that the operation has been correctly updated (or left alone). *)
@@ -592,14 +603,14 @@ let () =
     List.fold_left_s add_op prevalidation_state ops_and_outcomes
   in
   let final_proto_ophmap = get_mempool_operations final_prevalidation_state in
-  let final_bounding_ophset =
+  let final_bounding_ophmap =
     fst (get_bounding_state final_prevalidation_state)
   in
   assert (
     Operation_hash.Map.cardinal final_proto_ophmap
-    = Operation_hash.Set.cardinal final_bounding_ophset) ;
+    = Operation_hash.Map.cardinal final_bounding_ophmap) ;
   Operation_hash.Map.iter
-    (fun oph _ -> assert (Operation_hash.Set.mem oph final_bounding_ophset))
+    (fun oph _ -> assert (Operation_hash.Map.mem oph final_bounding_ophmap))
     final_proto_ophmap ;
   return_unit
 
@@ -627,7 +638,7 @@ let () =
   let oph = QCheck2.Gen.generate1 Generators.operation_hash_gen in
   let state = P.remove_operation state oph in
   assert (Operation_hash.Map.is_empty (get_mempool_operations state)) ;
-  assert (Operation_hash.Set.is_empty (fst (get_bounding_state state))) ;
+  assert (Operation_hash.Map.is_empty (fst (get_bounding_state state))) ;
   (* Prepare the initial state. *)
   let*! initial_state =
     List.fold_left_s
@@ -649,25 +660,25 @@ let () =
       let oph = random_oph_from_map proto_ophmap_before in
       let state = P.remove_operation state oph in
       let proto_ophmap = get_mempool_operations state in
-      let bounding_ophset = fst (get_bounding_state state) in
+      let bounding_ophmap = fst (get_bounding_state state) in
       assert (not (Operation_hash.Map.mem oph proto_ophmap)) ;
-      assert (not (Operation_hash.Set.mem oph bounding_ophset)) ;
+      assert (not (Operation_hash.Map.mem oph bounding_ophmap)) ;
       let cardinal = Operation_hash.Map.cardinal proto_ophmap in
       assert (cardinal = cardinal_before - 1) ;
-      assert (Operation_hash.Set.cardinal bounding_ophset = cardinal) ;
+      assert (Operation_hash.Map.cardinal bounding_ophmap = cardinal) ;
       (state, proto_ophmap, cardinal))
     else
       (* Remove a fresh operation. *)
-      let bounding_ophset_before = get_bounding_state state in
+      let bounding_ophmap_before = get_bounding_state state in
       let oph =
         QCheck2.Gen.generate1 (Generators.fresh_oph_gen proto_ophmap_before)
       in
       let state = P.remove_operation state oph in
       let proto_ophmap = get_mempool_operations state in
-      let bounding_ophset = get_bounding_state state in
+      let bounding_ophmap = get_bounding_state state in
       (* Internal states are physically unchanged. *)
       assert (proto_ophmap == proto_ophmap_before) ;
-      assert (bounding_ophset == bounding_ophset_before) ;
+      assert (bounding_ophmap == bounding_ophmap_before) ;
       (state, proto_ophmap, cardinal_before)
   in
   let rec fun_power f x n = if n <= 0 then x else fun_power f (f x) (n - 1) in
@@ -677,10 +688,10 @@ let () =
       (initial_state, initial_proto_ophmap, initial_cardinal)
       nb_ops_to_remove
   in
-  let final_bounding_ophset = fst (get_bounding_state final_state) in
-  assert (Operation_hash.Set.cardinal final_bounding_ophset = final_cardinal) ;
+  let final_bounding_ophmap = fst (get_bounding_state final_state) in
+  assert (Operation_hash.Map.cardinal final_bounding_ophmap = final_cardinal) ;
   assert (
     Operation_hash.Map.for_all
-      (fun oph _op -> Operation_hash.Set.mem oph final_bounding_ophset)
+      (fun oph _op -> Operation_hash.Map.mem oph final_bounding_ophmap)
       final_proto_ophmap) ;
   return_unit
diff --git a/src/lib_shell/test/test_prevalidator_bounding.ml b/src/lib_shell/test/test_prevalidator_bounding.ml
index 40fc0813eb05eb7908f2a1cdafe7959ad646722c..905f2ac4db65feb89fb5c391500c8ca593de7654 100644
--- a/src/lib_shell/test/test_prevalidator_bounding.ml
+++ b/src/lib_shell/test/test_prevalidator_bounding.ml
@@ -278,6 +278,10 @@ let make_op oph ~size ~weight =
     default_raw_op
     data
 
+let copy_op_with_size op size = make_op op.hash ~size ~weight:(weight op)
+
+let copy_op_with_weight op weight = make_op op.hash ~size:op.size ~weight
+
 let op_gen ~may_exceed_max_total_bytes =
   let open QCheck2.Gen in
   let* oph = oph_gen in
@@ -411,7 +415,7 @@ let () =
   assert (state == empty) ;
   (* Add an operation to the empty state. *)
   let state, replacements =
-    WithExceptions.Option.get ~loc:__LOC__ (add_operation empty config op)
+    WithExceptions.Result.get_ok ~loc:__LOC__ (add_operation empty config op)
   in
   (* Check that the state contains a single operation which is [op].
      Then the other fields are correct thanks to [check_invariants]. *)
@@ -422,16 +426,14 @@ let () =
   (* Removing the added operation goes back to an empty state. *)
   let state = remove_operation state op.hash in
   assert (state = empty) ;
-  (* Adding an operation larger than the max_total_bytes fails. *)
-  let over_max_op =
-    make_op op.hash ~size:(config.max_total_bytes + 1) ~weight:(weight op)
-  in
-  assert (Option.is_none (add_operation empty config over_max_op)) ;
+  (* Adding an operation larger than the max_total_bytes fails.
+     Moreover, there is no returned op_to_overtake, since the
+     operation can never be added to the state no matter its weight. *)
+  let over_max_op = copy_op_with_size op (config.max_total_bytes + 1) in
+  assert (add_operation empty config over_max_op = Error None) ;
   (* Adding an operation with exactly the max_total_bytes succeeds. *)
-  let max_op =
-    make_op op.hash ~size:config.max_total_bytes ~weight:(weight op)
-  in
-  assert (Option.is_some (add_operation empty config max_op)) ;
+  let max_op = copy_op_with_size op config.max_total_bytes in
+  assert (Result.is_ok (add_operation empty config max_op)) ;
   unit
 
 (** Return the cardinal and total size of all operations in opset that
@@ -477,26 +479,41 @@ let check_successful_add ?expected_nb_replacements ~state_before ~state
         ~error_msg:"Expected %L replacements but got %R.")
     expected_nb_replacements
 
+let check_failed_add state op ~op_to_overtake =
+  (* Failure to add an operation should only happen when removing all
+     operations that are smaller is not enough to make room for it. *)
+  let nb_smaller, size_smaller = nb_and_size_smaller op state.opset in
+  assert (
+    state.cardinal - nb_smaller + 1 > config_for_tests.max_operations
+    || state.total_bytes - size_smaller + op.size
+       > config_for_tests.max_total_bytes) ;
+  (* Moreover, op with a revised weight should be accepted by
+     the state if and only if it exceeds op_to_overtake. *)
+  match op_to_overtake with
+  | Some op_to_overtake ->
+      let weight_to_overtake = weight op_to_overtake in
+      let op_lighter = copy_op_with_weight op (weight_to_overtake - 1) in
+      assert (Result.is_error (add_operation state config_for_tests op_lighter)) ;
+      let op_heavier = copy_op_with_weight op (weight_to_overtake + 1) in
+      assert (Result.is_ok (add_operation state config_for_tests op_heavier))
+      (* (We don't test with exactly the same weight as op_to_overtake,
+          because then the hashes would be used as a tie-breaker.) *)
+  | None ->
+      (* If op_to_overtake is None then the operation cannot be added, no
+         matter its weight. We test with a weight much higher than all
+         weights in the state (see [weight_gen]). *)
+      let op_heaviest = copy_op_with_weight op 10_000 in
+      assert (Result.is_error (add_operation state config_for_tests op_heaviest))
+
 (* Preconditions:
    - [state_before] verifies the state invariants
    - [op] is not in [state_before] *)
 let check_add_fresh state_before op =
   assert (not (Operation_hash.Map.mem op.hash state_before.ophmap)) ;
   match add_operation state_before config_for_tests op with
-  | Some (state, replacements) ->
-      (* The new operation has been successfully added. *)
+  | Ok (state, replacements) ->
       check_successful_add ~state_before ~state ~replacements op
-  | None ->
-      (* The new operation could not be added. This should only happen
-         when removing all operations that are smaller is not enough to
-         make room for it. *)
-      let nb_smaller, size_smaller =
-        nb_and_size_smaller op state_before.opset
-      in
-      assert (
-        state_before.cardinal - nb_smaller + 1 > config_for_tests.max_operations
-        || state_before.total_bytes - size_smaller + op.size
-           > config_for_tests.max_total_bytes)
+  | Error op_to_overtake -> check_failed_add state_before op ~op_to_overtake
 
 (* Preconditions:
    - [state_before] verifies the state invariants
@@ -506,7 +523,7 @@ let check_add_present state_before op =
   let res = add_operation state_before config_for_tests op in
   (* add_operation should return the same state (physical equality
      intended) and an empty list of replacements. *)
-  let state, replacements = WithExceptions.Option.get ~loc:__LOC__ res in
+  let state, replacements = WithExceptions.Result.get_ok ~loc:__LOC__ res in
   assert (state == state_before) ;
   assert (List.is_empty replacements)
 
@@ -572,13 +589,20 @@ let () =
 
 let check_add_fails ~__LOC__ state op =
   Log.debug "Check failure: add op %a to %a" pp_op op pp_state state ;
-  if Option.is_some (add_operation state config_for_tests op) then
-    Test.fail "%s: add_operation unexpectedly succeeded." __LOC__
+  match add_operation state config_for_tests op with
+  | Ok _ -> Test.fail "%s: add_operation unexpectedly succeeded." __LOC__
+  | Error op_to_overtake -> (
+      try check_failed_add state op ~op_to_overtake
+      with exn ->
+        Test.fail
+          "%s: Problem while checking failure of add_operation:\n%s"
+          __LOC__
+          (Printexc.to_string exn))
 
 let add_successfully ~__LOC__ ~expected_nb_replacements state_before op =
   Log.debug "Check success: add op %a to %a" pp_op op pp_state state_before ;
   let ((state, replacements) as res) =
-    WithExceptions.Option.get ~loc:__LOC__
+    WithExceptions.Result.get_ok ~loc:__LOC__
     @@ add_operation state_before config_for_tests op
   in
   (try
diff --git a/src/lib_shell_services/validation_errors.ml b/src/lib_shell_services/validation_errors.ml
index 0d70f8375687bf01f42f523ef1679278e0ba6731..d1e8c8216959b40cb2106ca6d027a48bcfa95a2e 100644
--- a/src/lib_shell_services/validation_errors.ml
+++ b/src/lib_shell_services/validation_errors.ml
@@ -34,7 +34,10 @@ type error +=
       old_hash : Operation_hash.t;
       new_hash : Operation_hash.t;
     }
-  | Rejected_by_full_mempool of Operation_hash.t
+  | Rejected_by_full_mempool of {
+      hash : Operation_hash.t;
+      needed_fee_in_mutez : int64 option;
+    }
   | Removed_from_full_mempool of Operation_hash.t
 
 type error += Too_many_operations
@@ -110,16 +113,37 @@ let () =
     ~id:"node.mempool.rejected_by_full_mempool"
     ~title:"Operation fees are too low to be considered in full mempool"
     ~description:"Operation fees are too low to be considered in full mempool"
-    ~pp:(fun ppf oph ->
+    ~pp:(fun ppf (oph, fee_opt) ->
       Format.fprintf
         ppf
-        "The mempool is full and operation %a does not have enough fees to \
-         replace existing operations."
+        "Operation %a has been rejected because the mempool is full. %s"
         Operation_hash.pp
-        oph)
-    Data_encoding.(obj1 (req "operation_hash" Operation_hash.encoding))
-    (function Rejected_by_full_mempool oph -> Some oph | _ -> None)
-    (fun oph -> Rejected_by_full_mempool oph) ;
+        oph
+        (match fee_opt with
+        | Some fee ->
+            Format.sprintf
+              "This specific operation would need a total fee of at least %Ld \
+               mutez to be considered and propagated by the mempool of this \
+               particular node right now. Note that if the node receives \
+               operations with a better fee over gas limit ratio in the \
+               future, the operation may be rejected even with the indicated \
+               fee, or it may be successfully injected but removed at a later \
+               date."
+              fee
+        | None ->
+            "The operation cannot be accepted by this node at the moment, \
+             regardless of its fee. Try again after the next block has been \
+             baked."))
+    Data_encoding.(
+      obj2
+        (req "operation_hash" Operation_hash.encoding)
+        (req "needed_fee_in_mutez" (option int64)))
+    (function
+      | Rejected_by_full_mempool {hash; needed_fee_in_mutez} ->
+          Some (hash, needed_fee_in_mutez)
+      | _ -> None)
+    (fun (hash, needed_fee_in_mutez) ->
+      Rejected_by_full_mempool {hash; needed_fee_in_mutez}) ;
   (* Removed_from_full_mempool *)
   register_error_kind
     `Temporary
diff --git a/src/lib_shell_services/validation_errors.mli b/src/lib_shell_services/validation_errors.mli
index 7ac0343a7ae46bb77d76be244745f28bc061feec..3c0d92a6df9d6ce07e58da64420c34e084b80344 100644
--- a/src/lib_shell_services/validation_errors.mli
+++ b/src/lib_shell_services/validation_errors.mli
@@ -34,7 +34,10 @@ type error +=
       old_hash : Operation_hash.t;
       new_hash : Operation_hash.t;
     }
-  | Rejected_by_full_mempool of Operation_hash.t
+  | Rejected_by_full_mempool of {
+      hash : Operation_hash.t;
+      needed_fee_in_mutez : int64 option;
+    }
   | Removed_from_full_mempool of Operation_hash.t
 
 type error += Too_many_operations
diff --git a/tezt/lib_tezos/constant.ml b/tezt/lib_tezos/constant.ml
index 0cb83e054c8b20e003c1731846df82f6ccdbbb7d..4a8c8e6591d3b06977940e522fd29bfac057a32d 100644
--- a/tezt/lib_tezos/constant.ml
+++ b/tezt/lib_tezos/constant.ml
@@ -132,6 +132,11 @@ module Error_msg = struct
 
   let rejected_by_full_mempool =
     rex
-      "The mempool is full and operation (.*) does not have enough fees to \
-       replace existing operations"
+      "Operation (.*) has been rejected because the mempool is full. This \
+       specific operation would need a total fee of at least (.*) mutez to be \
+       considered and propagated by the mempool of this particular node right \
+       now. Note that if the node receives operations with a better fee over \
+       gas limit ratio in the future, the operation may be rejected even with \
+       the indicated fee, or it may be successfully injected but removed at a \
+       later date."
 end
diff --git a/tezt/tests/prevalidator.ml b/tezt/tests/prevalidator.ml
index bd1b57ee30c5c88a15c6d5de929c53fd58ee5724..54be3e225398775b430df3ac92fe8e926956bdb1 100644
--- a/tezt/tests/prevalidator.ml
+++ b/tezt/tests/prevalidator.ml
@@ -1540,6 +1540,17 @@ module Revamped = struct
     let* () = check_mempool ~applied:[oph4; oph3; oph2; oph1] client1 in
     check_mempool ~applied:[oph4; oph3; oph2; oph1] client2
 
+  let check_process_error_and_capture_two_groups ?__LOC__ rex process =
+    let* stderr = Process.check_and_read_stderr ~expect_failure:true process in
+    match stderr =~** rex with
+    | None ->
+        Test.fail
+          ?__LOC__
+          "Process was expected to fail with:\n%s\nbut instead failed with:\n%s"
+          (show_rex rex)
+          stderr
+    | Some groups -> return groups
+
   let test_full_mempool =
     Protocol.register_test
       ~__FILE__
@@ -1601,9 +1612,10 @@ module Revamped = struct
       4
       "The client should report when the mempool is full and not enough fees \
        are provided." ;
-    let* () =
-      Process.check_error
-        ~msg:Constant.Error_msg.rejected_by_full_mempool
+    let* _oph, recommended_fee =
+      check_process_error_and_capture_two_groups
+        ~__LOC__
+        Constant.Error_msg.rejected_by_full_mempool
         (Client.spawn_transfer
            ~giver:Constant.bootstrap5.alias
            ~receiver:Constant.bootstrap2.alias
@@ -1612,6 +1624,10 @@ module Revamped = struct
            ~gas_limit
            client1)
     in
+    Check.(
+      (recommended_fee = string_of_int (fee + 1))
+        string
+        ~error_msg:"The recommended fee is %L but expected %R.") ;
 
     log_step 5 "Force inject an extra operation with not enough fees." ;
     let* (`OpHash oph5) =