diff --git a/src/net_processing.cpp b/src/net_processing.cpp
--- a/src/net_processing.cpp
+++ b/src/net_processing.cpp
@@ -1760,8 +1760,8 @@
 }
 
 static bool AlreadyHaveProof(const avalanche::ProofId &proofid) {
-    // TODO check if the proof is in the orphan pool as well
-    return g_avalanche && g_avalanche->getProof(proofid);
+    return g_avalanche &&
+           (g_avalanche->getProof(proofid) || g_avalanche->getOrphan(proofid));
 }
 
 void RelayTransaction(const TxId &txid, const CConnman &connman) {
diff --git a/test/functional/p2p_inv_download.py b/test/functional/p2p_inv_download.py
--- a/test/functional/p2p_inv_download.py
+++ b/test/functional/p2p_inv_download.py
@@ -7,7 +7,10 @@
 """
 
 from test_framework.address import ADDRESS_BCHREG_UNSPENDABLE
+from test_framework.avatools import wait_for_proof
+from test_framework.key import ECKey, bytes_to_wif
 from test_framework.messages import (
+    AvalancheProof,
     CInv,
     CTransaction,
     FromHex,
@@ -362,6 +365,45 @@
         self.nodes[0].p2ps[0].send_message(
             msg_notfound(vec=[CInv(context.inv_type, 1)]))
 
+    @skip(TX_TEST_CONTEXT)
+    def test_orphan_download(self, context):
+        node = self.nodes[0]
+        privkey = ECKey()
+        privkey.generate()
+        privkey_wif = bytes_to_wif(privkey.get_bytes())
+
+        # Build a proof with missing utxos so it will be orphaned
+        orphan = node.buildavalancheproof(
+            42, 2000000000, privkey.get_pubkey().get_bytes().hex(), [{
+                'txid': '0' * 64,
+                'vout': 0,
+                'amount': 10,
+                'height': 42,
+                'iscoinbase': False,
+                'privatekey': privkey_wif,
+            }]
+        )
+        proofid = FromHex(AvalancheProof(), orphan).proofid
+        proofid_hex = "{:064x}".format(proofid)
+
+        self.restart_node(0, extra_args=self.extra_args[0] + [
+            "-avaproof={}".format(orphan),
+            "-avamasterkey={}".format(privkey_wif),
+        ])
+        node.generate(2)
+        wait_for_proof(node, proofid_hex)
+        assert_equal(node.getrawavalancheproof(proofid_hex)["orphan"], True)
+
+        peer = node.add_p2p_connection(context.p2p_conn())
+        peer.send_message(msg_inv([CInv(t=context.inv_type, h=proofid)]))
+
+        # Give enough time for the node to eventually request the proof.
+        node.setmocktime(int(time.time()) +
+                         context.constants.getdata_interval + 1)
+        peer.sync_with_ping()
+
+        assert_equal(peer.getdata_count, 0)
+
     def run_test(self):
         for context in [TX_TEST_CONTEXT, PROOF_TEST_CONTEXT]:
             self.log.info(
@@ -381,7 +423,7 @@
             # Run each test against new bitcoind instances, as setting mocktimes has long-term effects on when
             # the next trickle relay event happens.
             for test in [self.test_in_flight_max,
-                         self.test_inv_block, self.test_data_requests]:
+                         self.test_inv_block, self.test_data_requests, self.test_orphan_download]:
                 self.stop_nodes()
                 self.start_nodes()
                 self.connect_nodes(1, 0)
diff --git a/test/functional/test_framework/avatools.py b/test/functional/test_framework/avatools.py
--- a/test/functional/test_framework/avatools.py
+++ b/test/functional/test_framework/avatools.py
@@ -6,6 +6,7 @@
 
 from typing import Any, Optional, List, Dict
 
+from .authproxy import JSONRPCException
 from .messages import (
     AvalancheProof,
     CTransaction,
@@ -13,7 +14,10 @@
     ToHex
 )
 from .test_node import TestNode
-from .util import satoshi_round
+from .util import (
+    satoshi_round,
+    wait_until,
+)
 
 
 def create_coinbase_stakes(
@@ -120,3 +124,13 @@
 def get_proof_ids(node):
     return [FromHex(AvalancheProof(), peer['proof']
                     ).proofid for peer in node.getavalanchepeerinfo()]
+
+
+def wait_for_proof(node, proofid_hex, timeout=60):
+    def proof_found():
+        try:
+            node.getrawavalancheproof(proofid_hex)
+            return True
+        except JSONRPCException:
+            return False
+    wait_until(proof_found, timeout=timeout)