diff --git a/src/avalanche/peermanager.h b/src/avalanche/peermanager.h
--- a/src/avalanche/peermanager.h
+++ b/src/avalanche/peermanager.h
@@ -389,6 +389,8 @@
     bool addNodeToPeer(const PeerSet::iterator &it);
     bool removeNodeFromPeer(const PeerSet::iterator &it, uint32_t count = 1);
 
+    void cleanup();
+
     friend struct ::avalanche::TestPeerManager;
 };
 
diff --git a/src/avalanche/peermanager.cpp b/src/avalanche/peermanager.cpp
--- a/src/avalanche/peermanager.cpp
+++ b/src/avalanche/peermanager.cpp
@@ -795,4 +795,12 @@
     m_unbroadcast_proofids.erase(proofid);
 }
 
+void PeerManager::cleanup() {
+    auto now = GetTime<std::chrono::seconds>();
+
+    // Cleanup the orphan proofs. Consider obsolete any proof that has been
+    // registered more than 30 minutes ago.
+    orphanProofPool.removeObsoleteProofs(std::max(0s, now - 30min));
+}
+
 } // namespace avalanche
diff --git a/src/avalanche/proofpool.h b/src/avalanche/proofpool.h
--- a/src/avalanche/proofpool.h
+++ b/src/avalanche/proofpool.h
@@ -141,6 +141,9 @@
 
     std::optional<int64_t> getRegistrationTime(const ProofId &proofid) const;
 
+    /** Remove all proofs that have been registered before the cutoff time */
+    void removeObsoleteProofs(std::chrono::seconds cutoffTime);
+
     size_t size() const { return pool.size(); }
     size_t countProofs() { return registrationTimes.size(); };
 };
diff --git a/src/avalanche/proofpool.cpp b/src/avalanche/proofpool.cpp
--- a/src/avalanche/proofpool.cpp
+++ b/src/avalanche/proofpool.cpp
@@ -141,4 +141,16 @@
     return std::make_optional(it->registrationTime);
 }
 
+void ProofPool::removeObsoleteProofs(std::chrono::seconds cutoffTime) {
+    auto &timeView = registrationTimes.get<by_registration_time>();
+    auto &poolView = pool.get<by_proofid>();
+
+    auto lowerBound = timeView.lower_bound(cutoffTime.count());
+    for (auto it = timeView.begin(); it != lowerBound; it++) {
+        poolView.erase(it->proofid);
+    }
+
+    timeView.erase(timeView.begin(), timeView.lower_bound(cutoffTime.count()));
+}
+
 } // namespace avalanche
diff --git a/src/avalanche/test/peermanager_tests.cpp b/src/avalanche/test/peermanager_tests.cpp
--- a/src/avalanche/test/peermanager_tests.cpp
+++ b/src/avalanche/test/peermanager_tests.cpp
@@ -56,6 +56,8 @@
 
             return scores;
         }
+
+        static void cleanup(PeerManager &pm) { pm.cleanup(); }
     };
 
     static void addCoin(const COutPoint &outpoint, const CKey &key,
@@ -1836,4 +1838,66 @@
     }
 }
 
+BOOST_AUTO_TEST_CASE(cleanup) {
+    avalanche::PeerManager pm;
+
+    auto buildOrphan = [&]() {
+        const CKey key = CKey::MakeCompressedKey();
+        return buildProofWithOutpoints(key, {{TxId(GetRandHash()), 0}},
+                                       10 * COIN);
+    };
+
+    auto setMockTime = [&](const std::chrono::seconds mocktime) {
+        SetMockTime(mocktime.count());
+    };
+    auto now = GetTime<std::chrono::seconds>();
+
+    auto checkOrphan = [&](const ProofRef &proof, bool expectOrphan) {
+        BOOST_CHECK_EQUAL(pm.isOrphan(proof->getId()), expectOrphan);
+        BOOST_CHECK_EQUAL(pm.exists(proof->getId()), expectOrphan);
+        BOOST_CHECK_EQUAL(!!pm.getProofRegistrationTime(proof->getId()),
+                          expectOrphan);
+    };
+
+    std::vector<ProofRef> proofs;
+    for (size_t i = 0; i < 10; i++) {
+        setMockTime(now + i * 1s);
+
+        auto proof = buildOrphan();
+        BOOST_CHECK(proof != nullptr);
+
+        BOOST_CHECK(!pm.registerProof(proof));
+        checkOrphan(proof, true);
+
+        proofs.push_back(std::move(proof));
+    }
+
+    // The orphans are not expired yet
+    TestPeerManager::cleanup(pm);
+    for (const auto &proof : proofs) {
+        checkOrphan(proof, true);
+    }
+
+    setMockTime(now + 30min);
+    // The orphans are not expired yet
+    TestPeerManager::cleanup(pm);
+    for (const auto &proof : proofs) {
+        checkOrphan(proof, true);
+    }
+
+    setMockTime(now + 30min + 5s);
+    // The first half of the orphans are now expired
+    TestPeerManager::cleanup(pm);
+    for (size_t i = 0; i < 10; i++) {
+        checkOrphan(proofs[i], i > 4);
+    }
+
+    setMockTime(now + 30min + 10s);
+    // Now they're all expired
+    TestPeerManager::cleanup(pm);
+    for (const auto &proof : proofs) {
+        checkOrphan(proof, false);
+    }
+}
+
 BOOST_AUTO_TEST_SUITE_END()
diff --git a/src/avalanche/test/proofpool_tests.cpp b/src/avalanche/test/proofpool_tests.cpp
--- a/src/avalanche/test/proofpool_tests.cpp
+++ b/src/avalanche/test/proofpool_tests.cpp
@@ -466,4 +466,52 @@
     }
 }
 
+BOOST_AUTO_TEST_CASE(remove_obsolete_proofs) {
+    ProofPool testPool;
+
+    // Calling when there is no proof has no effect
+    testPool.removeObsoleteProofs(0s);
+    testPool.removeObsoleteProofs(GetTime<std::chrono::seconds>());
+    testPool.removeObsoleteProofs(-1s);
+
+    auto now = GetTime<std::chrono::seconds>();
+    auto mocktime = now;
+
+    auto elapseTime = [&](std::chrono::seconds seconds) {
+        mocktime += seconds;
+        SetMockTime(mocktime.count());
+    };
+    elapseTime(0s);
+
+    std::vector<ProofRef> proofs;
+    for (size_t i = 0; i < 10; i++) {
+        auto proof = buildRandomProof(MIN_VALID_PROOF_SCORE);
+        BOOST_CHECK(testPool.addProofIfNoConflict(proof));
+
+        proofs.push_back(std::move(proof));
+
+        elapseTime(1s);
+    }
+
+    BOOST_CHECK_EQUAL(testPool.countProofs(), 10);
+
+    testPool.removeObsoleteProofs(0s);
+    BOOST_CHECK_EQUAL(testPool.countProofs(), 10);
+
+    testPool.removeObsoleteProofs(now);
+    BOOST_CHECK_EQUAL(testPool.countProofs(), 10);
+
+    for (size_t i = 0; i < 10; i++) {
+        testPool.removeObsoleteProofs(now + 5s);
+        BOOST_CHECK_EQUAL(testPool.countProofs(), 5);
+        for (size_t j = 0; j < 10; j++) {
+            BOOST_CHECK_EQUAL(!testPool.getRegistrationTime(proofs[j]->getId()),
+                              j < 5);
+        }
+    }
+
+    testPool.removeObsoleteProofs(now + 10s);
+    BOOST_CHECK_EQUAL(testPool.countProofs(), 0);
+}
+
 BOOST_AUTO_TEST_SUITE_END()