diff --git a/src/avalanche/processor.h b/src/avalanche/processor.h
--- a/src/avalanche/processor.h
+++ b/src/avalanche/processor.h
@@ -249,12 +249,6 @@
     class NotificationsHandler;
     std::unique_ptr<interfaces::Handler> chainNotificationsHandler;
 
-    /**
-     * Flag indicating that the proof must be registered at first new block
-     * after IBD
-     */
-    bool mustRegisterProof = false;
-
     Processor(interfaces::Chain &chain, CConnman *connmanIn,
               NodePeerManager *nodePeerManagerIn,
               std::unique_ptr<PeerData> peerDataIn, CKey sessionKeyIn);
diff --git a/src/avalanche/processor.cpp b/src/avalanche/processor.cpp
--- a/src/avalanche/processor.cpp
+++ b/src/avalanche/processor.cpp
@@ -209,10 +209,9 @@
     void updatedBlockTip() override {
         LOCK(m_processor->cs_peerManager);
 
-        if (m_processor->mustRegisterProof &&
-            !::ChainstateActive().IsInitialBlockDownload()) {
-            m_processor->peerManager->getPeerId(m_processor->peerData->proof);
-            m_processor->mustRegisterProof = false;
+        if (m_processor->peerData && m_processor->peerData->proof) {
+            m_processor->peerManager->registerProof(
+                m_processor->peerData->proof);
         }
 
         m_processor->peerManager->updatedBlockTip();
@@ -225,10 +224,7 @@
     : connman(connmanIn), nodePeerManager(nodePeerManagerIn),
       queryTimeoutDuration(AVALANCHE_DEFAULT_QUERY_TIMEOUT), round(0),
       peerManager(std::make_unique<PeerManager>()),
-      peerData(std::move(peerDataIn)), sessionKey(std::move(sessionKeyIn)),
-      // Schedule proof registration at the first new block after IBD.
-      // FIXME: get rid of this flag
-      mustRegisterProof(!!peerData) {
+      peerData(std::move(peerDataIn)), sessionKey(std::move(sessionKeyIn)) {
     // Make sure we get notified of chain state changes.
     chainNotificationsHandler =
         chain.handleNotifications(std::make_shared<NotificationsHandler>(this));
diff --git a/test/functional/abc_rpc_avalancheproof.py b/test/functional/abc_rpc_avalancheproof.py
--- a/test/functional/abc_rpc_avalancheproof.py
+++ b/test/functional/abc_rpc_avalancheproof.py
@@ -11,6 +11,7 @@
     create_coinbase_stakes,
     create_stakes,
     get_proof_ids,
+    wait_for_proof,
 )
 from test_framework.key import ECKey, bytes_to_wif
 from test_framework.messages import (
@@ -25,6 +26,7 @@
 from test_framework.util import (
     append_config,
     assert_equal,
+    connect_nodes,
     wait_until,
     assert_raises_rpc_error,
 )
@@ -48,12 +50,17 @@
 class AvalancheProofTest(BitcoinTestFramework):
     def set_test_params(self):
         self.setup_clean_chain = True
-        self.num_nodes = 1
-        self.extra_args = [['-enableavalanche=1', '-avacooldown=0'], ]
+        self.num_nodes = 2
+        self.extra_args = [['-enableavalanche=1', '-avacooldown=0'],
+                           ['-enableavalanche=1', '-avacooldown=0']]
         self.supports_cli = False
         self.rpc_timeout = 120
 
     def run_test(self):
+        # Turn off node 1 while node 0 mines blocks to generate stakes,
+        # so that we can later try starting node 1 with an orphan proof.
+        self.stop_node(1)
+
         node = self.nodes[0]
 
         addrkey0 = node.get_deterministic_priv_key()
@@ -101,25 +108,37 @@
         assert_raises_rpc_error(-22, "Proof has invalid format",
                                 node.decodeavalancheproof, proof[:-2])
 
-        # Restart the node, making sure it is initially in IBD mode
-        minchainwork = int(node.getblockchaininfo()["chainwork"], 16) + 1
+        # Restart the node with this proof
         self.restart_node(0, self.extra_args[0] + [
             "-avaproof={}".format(proof),
             "-avamasterkey=cND2ZvtabDbJ1gucx9GWH6XT9kgTAqfb6cotPt5Q5CyxVDhid2EN",
-            "-minimumchainwork=0x{:x}".format(minchainwork),
         ])
 
-        self.log.info(
-            "The proof verification should be delayed until IBD is complete")
-        assert node.getblockchaininfo()["initialblockdownload"] is True
-        # Our proof cannot be verified during IBD, so we should have no peer
-        assert not node.getavalanchepeerinfo()
-        # Mining one more block should cause us to leave IBD
+        self.log.info("The proof is registered at first chaintip update")
+        assert_equal(len(node.getavalanchepeerinfo()), 0)
         node.generate(1)
-        # Our proof is now verified and our node is added as a peer
-        assert node.getblockchaininfo()["initialblockdownload"] is False
         wait_until(lambda: len(node.getavalanchepeerinfo()) == 1, timeout=5)
 
+        # This case will occur for users building proofs with a third party
+        # tool and then starting a new node that is not yet aware of the
+        # transactions used for stakes.
+        self.log.info("Start a node with an orphan proof")
+
+        self.start_node(1, self.extra_args[0] + [
+            "-avaproof={}".format(proof),
+            "-avamasterkey=cND2ZvtabDbJ1gucx9GWH6XT9kgTAqfb6cotPt5Q5CyxVDhid2EN",
+        ])
+        # Mine a block to trigger an attempt at registering the proof
+        self.nodes[1].generate(1)
+        wait_for_proof(self.nodes[1], f"{proofobj.proofid:0{64}x}",
+                       expect_orphan=True)
+
+        self.log.info("Connect to an up-to-date node to unorphan the proof")
+        connect_nodes(self.nodes[1], node)
+        self.sync_all()
+        wait_for_proof(self.nodes[1], f"{proofobj.proofid:0{64}x}",
+                       expect_orphan=False)
+
         if self.is_wallet_compiled():
             self.log.info(
                 "A proof using the maximum number of stakes is accepted...")