diff --git a/src/avalanche/peermanager.cpp b/src/avalanche/peermanager.cpp
--- a/src/avalanche/peermanager.cpp
+++ b/src/avalanche/peermanager.cpp
@@ -166,6 +166,7 @@
 
 void PeerManager::updatedBlockTip() {
     std::vector<PeerId> invalidPeers;
+    std::vector<Proof *> noLongerOrphans;
 
     {
         LOCK(cs_main);
@@ -176,12 +177,32 @@
             if (!p.proof.verify(state, coins)) {
                 invalidPeers.push_back(p.peerid);
             }
+            // TODO: find out if the coin got spent, or just dropped from
+            //  the mempool and can potentially be resubmitted again (orphan)
+        }
+
+        for (auto &[id, proof] : orphanProofs) {
+            ProofValidationState state;
+            if (fetchOrCreatePeer(proof, state) != peers.end()) {
+                noLongerOrphans.push_back(&proof);
+            } else if (state.GetResult() !=
+                       ProofValidationResult::MISSING_UTXO) {
+                // An orphan proof can become bad after we find the specified
+                // txid and it turns out to not match the amount, or the block
+                // height, or the destination type pkhash...
+                noLongerOrphans.push_back(&proof);
+                recentProofRejects->insert(proof.getId());
+            }
         }
     }
 
     for (const auto &pid : invalidPeers) {
         removePeer(pid);
     }
+
+    for (const auto &proof : noLongerOrphans) {
+        orphanProofs.erase(proof->getId());
+    }
 }
 
 PeerId PeerManager::getPeerId(const Proof &proof) {