diff --git a/src/avalanche/peermanager.h b/src/avalanche/peermanager.h
--- a/src/avalanche/peermanager.h
+++ b/src/avalanche/peermanager.h
@@ -9,6 +9,7 @@
 #include <avalanche/proof.h>
 #include <avalanche/proofpool.h>
 #include <avalanche/proofradixtreeadapter.h>
+#include <bloom.h>
 #include <coins.h>
 #include <consensus/validation.h>
 #include <pubkey.h>
@@ -140,6 +141,7 @@
     CONFLICTING,
     REJECTED,
     COOLDOWN_NOT_ELAPSED,
+    DANGLING,
 };
 
 class ProofRegistrationState : public ValidationState<ProofRegistrationResult> {
@@ -219,6 +221,15 @@
      */
     std::unordered_set<ProofId, SaltedProofIdHasher> m_unbroadcast_proofids;
 
+    /**
+     * Remember the last proofs that have been evicted because they had no node
+     * attached.
+     * A false positive would cause the proof to fail to register if there is
+     * no previously known node that is claiming it, which is acceptable
+     * intended the low expected false positive rate.
+     */
+    CRollingBloomFilter danglingProofIds{10000, 0.00001};
+
     /**
      * Quorum management.
      */
diff --git a/src/avalanche/peermanager.cpp b/src/avalanche/peermanager.cpp
--- a/src/avalanche/peermanager.cpp
+++ b/src/avalanche/peermanager.cpp
@@ -220,6 +220,13 @@
                           "proof-already-registered");
     }
 
+    if (danglingProofIds.contains(proofid) &&
+        pendingNodes.count(proofid) == 0) {
+        // Don't attempt to register a proof that we already evicted because it
+        // was dangling.
+        return invalidate(ProofRegistrationResult::DANGLING, "dangling-proof");
+    }
+
     // Check the proof's validity.
     ProofValidationState validationState;
     if (!WITH_LOCK(cs_main,
@@ -407,18 +414,19 @@
 void PeerManager::cleanupDanglingProofs() {
     const auto now = GetTime<std::chrono::seconds>();
 
-    std::vector<ProofId> danglingProofIds;
+    std::vector<ProofId> newlyDanglingProofIds;
     for (const Peer &peer : peers) {
         // If the peer has been registered for some time and has no node
         // attached, discard it.
         if (peer.node_count == 0 &&
             (peer.registration_time + Peer::DANGLING_TIMEOUT) <= now) {
-            danglingProofIds.push_back(peer.getProofId());
+            newlyDanglingProofIds.push_back(peer.getProofId());
         }
     }
 
-    for (const ProofId &proofid : danglingProofIds) {
+    for (const ProofId &proofid : newlyDanglingProofIds) {
         rejectProof(proofid, RejectionMode::INVALIDATE);
+        danglingProofIds.insert(proofid);
     }
 }
 
diff --git a/test/functional/abc_feature_proof_cleanup.py b/test/functional/abc_feature_proof_cleanup.py
--- a/test/functional/abc_feature_proof_cleanup.py
+++ b/test/functional/abc_feature_proof_cleanup.py
@@ -13,8 +13,10 @@
     get_ava_p2p_interface,
     get_proof_ids,
 )
+from test_framework.key import ECKey
 from test_framework.test_framework import BitcoinTestFramework
 from test_framework.util import assert_equal
+from test_framework.wallet_util import bytes_to_wif
 
 # Interval between 2 proof cleanups
 AVALANCHE_CLEANUP_INTERVAL = 5 * 60
@@ -28,6 +30,9 @@
         self.extra_args = [[
             '-enableavalanche=1',
             '-avaproofstakeutxoconfirmations=1',
+            '-enableavalanchepeerdiscovery=1',
+            # Get rid of the getdata delay penalty for inbounds
+            '-whitelist=noban@127.0.0.1',
         ]] * self.num_nodes
 
     def run_test(self):
@@ -37,6 +42,7 @@
         node.setmocktime(mocktime)
 
         proofs = []
+        keys = []
         peers = []
         # The first 5 peers have a node attached
         for _ in range(5):
@@ -49,6 +55,7 @@
                 proof.serialize().hex())
 
             proofs.append(proof)
+            keys.append(key)
             peers.append(peer)
 
         # The last 5 peers have no node attached
@@ -91,6 +98,42 @@
         node.mockscheduler(AVALANCHE_CLEANUP_INTERVAL)
         self.wait_until(lambda: get_proof_ids(node) == [])
 
+        self.log.info("Check the cleaned up proofs are no longer accepted...")
+
+        sender = get_ava_p2p_interface(node)
+        for proof in proofs:
+            with node.assert_debug_log(["dangling-proof"]):
+                sender.send_avaproof(proof)
+
+        assert_equal(get_proof_ids(node), [])
+
+        self.log.info("...until there is a node to attach")
+
+        node.disconnect_p2ps()
+        assert_equal(len(node.p2ps), 0)
+
+        avanode = get_ava_p2p_interface(node)
+
+        avanode_key = keys[0]
+        avanode_proof = proofs[0]
+
+        delegated_key = ECKey()
+        delegated_key.generate()
+
+        delegation = node.delegateavalancheproof(
+            f"{avanode_proof.limited_proofid:064x}",
+            bytes_to_wif(avanode_key.get_bytes()),
+            delegated_key.get_pubkey().get_bytes().hex(),
+        )
+
+        avanode.send_avahello(delegation, delegated_key)
+        avanode.sync_with_ping()
+        avanode.wait_until(lambda: avanode.last_message.get(
+            "getdata") and avanode.last_message["getdata"].inv[-1].hash == avanode_proof.proofid)
+
+        avanode.send_avaproof(avanode_proof)
+        self.wait_until(lambda: avanode_proof.proofid in get_proof_ids(node))
+
 
 if __name__ == '__main__':
     ProofsCleanupTest().main()