diff --git a/src/net_processing.cpp b/src/net_processing.cpp
--- a/src/net_processing.cpp
+++ b/src/net_processing.cpp
@@ -2778,8 +2778,8 @@
             return true;
         }
 
-        std::deque<COutPoint> vWorkQueue;
-        std::vector<TxId> vEraseQueue;
+        std::set<TxId> orphan_work_set;
+
         CTransactionRef ptx;
         vRecv >> ptx;
         const CTransaction &tx = *ptx;
@@ -2805,7 +2805,13 @@
             g_mempool.check(pcoinsTip.get());
             RelayTransaction(tx, connman);
             for (size_t i = 0; i < tx.vout.size(); i++) {
-                vWorkQueue.emplace_back(txid, i);
+                auto it_by_prev = mapOrphanTransactionsByPrev.find(
+                    COutPoint(txid, i));
+                if (it_by_prev != mapOrphanTransactionsByPrev.end()) {
+                    for (const auto &elem : it_by_prev->second) {
+                        orphan_work_set.insert(TxId(elem->first));
+                    }
+                }
             }
 
             pfrom->nLastTXTime = GetTime();
@@ -2819,77 +2825,77 @@
             // Recursively process any orphan transactions that depended on this
             // one
             std::unordered_map<NodeId, uint32_t> rejectCountPerNode;
-            while (!vWorkQueue.empty()) {
-                auto itByPrev =
-                    mapOrphanTransactionsByPrev.find(vWorkQueue.front());
-                vWorkQueue.pop_front();
-                if (itByPrev == mapOrphanTransactionsByPrev.end()) {
+            while (!orphan_work_set.empty()) {
+                const TxId orphanTxId = *orphan_work_set.begin();
+                orphan_work_set.erase(orphan_work_set.begin());
+
+                auto orphan_it = mapOrphanTransactions.find(orphanTxId);
+                if (orphan_it == mapOrphanTransactions.end()) {
                     continue;
                 }
-                for (auto mi = itByPrev->second.begin();
-                     mi != itByPrev->second.end(); ++mi) {
-                    const CTransactionRef &porphanTx = (*mi)->second.tx;
-                    const CTransaction &orphanTx = *porphanTx;
-                    const TxId &orphanId = orphanTx.GetId();
-                    NodeId fromPeer = (*mi)->second.fromPeer;
-                    bool fMissingInputs2 = false;
-                    // Use a dummy CValidationState so someone can't setup nodes
-                    // to counter-DoS based on orphan resolution (that is,
-                    // feeding people an invalid transaction based on LegitTxX
-                    // in order to get anyone relaying LegitTxX banned)
-                    CValidationState stateDummy;
-
-                    auto it = rejectCountPerNode.find(fromPeer);
-                    if (it != rejectCountPerNode.end() &&
-                        it->second > MAX_NON_STANDARD_ORPHAN_PER_NODE) {
-                        continue;
-                    }
 
-                    if (AcceptToMemoryPool(config, g_mempool, stateDummy,
-                                           porphanTx, &fMissingInputs2,
-                                           false /* bypass_limits */,
-                                           Amount::zero() /* nAbsurdFee */)) {
-                        LogPrint(BCLog::MEMPOOL, "   accepted orphan tx %s\n",
-                                 orphanId.ToString());
-                        RelayTransaction(orphanTx, connman);
-                        for (size_t i = 0; i < orphanTx.vout.size(); i++) {
-                            vWorkQueue.emplace_back(orphanId, i);
-                        }
-                        vEraseQueue.push_back(orphanId);
-                    } else if (!fMissingInputs2) {
-                        int nDos = 0;
-                        if (stateDummy.IsInvalid(nDos)) {
-                            rejectCountPerNode[fromPeer]++;
-                            if (nDos > 0) {
-                                // Punish peer that gave us an invalid orphan tx
-                                Misbehaving(fromPeer, nDos,
-                                            "invalid-orphan-tx");
-                                LogPrint(BCLog::MEMPOOL,
-                                         "   invalid orphan tx %s\n",
-                                         orphanId.ToString());
+                const CTransactionRef porphanTx = orphan_it->second.tx;
+                const CTransaction &orphanTx = *porphanTx;
+                NodeId fromPeer = orphan_it->second.fromPeer;
+                bool fMissingInputs2 = false;
+                // Use a dummy CValidationState so someone can't setup nodes to
+                // counter-DoS based on orphan resolution (that is, feeding
+                // people an invalid transaction based on LegitTxX in order to
+                // get anyone relaying LegitTxX banned)
+                CValidationState stateDummy;
+
+                auto it = rejectCountPerNode.find(fromPeer);
+                if (it != rejectCountPerNode.end() &&
+                    it->second > MAX_NON_STANDARD_ORPHAN_PER_NODE) {
+                    continue;
+                }
+
+                if (AcceptToMemoryPool(config, g_mempool, stateDummy, porphanTx,
+                                       &fMissingInputs2,
+                                       false /* bypass_limits */,
+                                       Amount::zero() /* nAbsurdFee */)) {
+                    LogPrint(BCLog::MEMPOOL, "   accepted orphan tx %s\n",
+                             orphanTxId.ToString());
+                    RelayTransaction(orphanTx, connman);
+                    for (size_t i = 0; i < orphanTx.vout.size(); i++) {
+                        auto it_by_prev = mapOrphanTransactionsByPrev.find(
+                            COutPoint(orphanTxId, i));
+                        if (it_by_prev != mapOrphanTransactionsByPrev.end()) {
+                            for (const auto &elem : it_by_prev->second) {
+                                orphan_work_set.insert(TxId(elem->first));
                             }
                         }
-                        // Has inputs but not accepted to mempool
-                        // Probably non-standard or insufficient fee
-                        LogPrint(BCLog::MEMPOOL, "   removed orphan tx %s\n",
-                                 orphanId.ToString());
-                        vEraseQueue.push_back(orphanId);
-                        if (!stateDummy.CorruptionPossible()) {
-                            // Do not use rejection cache for witness
-                            // transactions or witness-stripped transactions, as
-                            // they can have been malleated. See
-                            // https://github.com/bitcoin/bitcoin/issues/8279
-                            // for details.
-                            assert(recentRejects);
-                            recentRejects->insert(orphanId);
+                    }
+                    EraseOrphanTx(orphanTxId);
+                } else if (!fMissingInputs2) {
+                    int nDos = 0;
+                    if (stateDummy.IsInvalid(nDos)) {
+                        rejectCountPerNode[fromPeer]++;
+                        if (nDos > 0) {
+                            // Punish peer that gave us an invalid orphan tx
+                            Misbehaving(fromPeer, nDos, "invalid-orphan-tx");
+                            LogPrint(BCLog::MEMPOOL,
+                                     "   invalid orphan tx %s\n",
+                                     orphanTxId.ToString());
                         }
+                        EraseOrphanTx(orphanTxId);
                     }
-                    g_mempool.check(pcoinsTip.get());
+                    // Has inputs but not accepted to mempool
+                    // Probably non-standard or insufficient fee
+                    LogPrint(BCLog::MEMPOOL, "   removed orphan tx %s\n",
+                             orphanTxId.ToString());
+                    if (!stateDummy.CorruptionPossible()) {
+                        // Do not use rejection cache for witness
+                        // transactions or witness-stripped transactions, as
+                        // they can have been malleated. See
+                        // https://github.com/bitcoin/bitcoin/issues/8279
+                        // for details.
+                        assert(recentRejects);
+                        recentRejects->insert(orphanTxId);
+                    }
+                    EraseOrphanTx(orphanTxId);
                 }
-            }
-
-            for (const TxId &idOfOrphanTxToErase : vEraseQueue) {
-                EraseOrphanTx(idOfOrphanTxToErase);
+                g_mempool.check(pcoinsTip.get());
             }
         } else if (fMissingInputs) {
             // It may be the case that the orphans parents have all been