diff --git a/src/miner.cpp b/src/miner.cpp
--- a/src/miner.cpp
+++ b/src/miner.cpp
@@ -452,8 +452,17 @@
         }
 
         if (packageFees < blockMinFeeRate.GetFee(packageSize)) {
-            // Everything else we might consider has a lower fee rate
-            return;
+            // Don't include this package, but don't stop yet because something
+            // else we might consider may have a sufficient fee rate (since txes
+            // are ordered by virtualsize feerate, not actual feerate).
+            if (fUsingModified) {
+                // Since we always look at the best entry in mapModifiedTx, we
+                // must erase failed entries so that we can consider the next
+                // best entry on the next loop iteration
+                mapModifiedTx.get<ancestor_score>().erase(modit);
+                failedTx.insert(iter);
+            }
+            continue;
         }
 
         // The following must not use virtual size since TestPackage relies on
diff --git a/src/test/mempool_tests.cpp b/src/test/mempool_tests.cpp
--- a/src/test/mempool_tests.cpp
+++ b/src/test/mempool_tests.cpp
@@ -308,6 +308,11 @@
     LOCK2(cs_main, pool.cs);
     TestMemPoolEntryHelper entry;
 
+    /* Remove the default nonzero sigops, since the below tests are focussing on
+     * fee-based ordering and involve some artificially very tiny 21-byte
+     * transactions without any inputs. */
+    entry.SigOpCount(0);
+
     /* 3rd highest fee */
     CMutableTransaction tx1 = CMutableTransaction();
     tx1.vout.resize(1);
@@ -494,6 +499,11 @@
     LOCK2(cs_main, pool.cs);
     TestMemPoolEntryHelper entry;
 
+    /* Remove the default nonzero sigops, since the below tests are focussing on
+     * fee-based ordering and involve some artificially very tiny 21-byte
+     * transactions without any inputs. */
+    entry.SigOpCount(0);
+
     /* 3rd highest fee */
     CMutableTransaction tx1 = CMutableTransaction();
     tx1.vout.resize(1);
diff --git a/src/txmempool.h b/src/txmempool.h
--- a/src/txmempool.h
+++ b/src/txmempool.h
@@ -258,15 +258,17 @@
                           double &size) const {
         // Compare feerate with descendants to feerate of the transaction, and
         // return the fee/size for the max.
-        double f1 = a.GetSizeWithDescendants() * (a.GetModifiedFee() / SATOSHI);
-        double f2 = a.GetTxSize() * (a.GetModFeesWithDescendants() / SATOSHI);
+        double f1 =
+            a.GetVirtualSizeWithDescendants() * (a.GetModifiedFee() / SATOSHI);
+        double f2 =
+            a.GetTxVirtualSize() * (a.GetModFeesWithDescendants() / SATOSHI);
 
         if (f2 > f1) {
             mod_fee = a.GetModFeesWithDescendants() / SATOSHI;
-            size = a.GetSizeWithDescendants();
+            size = a.GetVirtualSizeWithDescendants();
         } else {
             mod_fee = a.GetModifiedFee() / SATOSHI;
-            size = a.GetTxSize();
+            size = a.GetTxVirtualSize();
         }
     }
 };
@@ -325,15 +327,17 @@
     void GetModFeeAndSize(const T &a, double &mod_fee, double &size) const {
         // Compare feerate with ancestors to feerate of the transaction, and
         // return the fee/size for the min.
-        double f1 = a.GetSizeWithAncestors() * (a.GetModifiedFee() / SATOSHI);
-        double f2 = a.GetTxSize() * (a.GetModFeesWithAncestors() / SATOSHI);
+        double f1 =
+            a.GetVirtualSizeWithAncestors() * (a.GetModifiedFee() / SATOSHI);
+        double f2 =
+            a.GetTxVirtualSize() * (a.GetModFeesWithAncestors() / SATOSHI);
 
         if (f1 > f2) {
             mod_fee = a.GetModFeesWithAncestors() / SATOSHI;
-            size = a.GetSizeWithAncestors();
+            size = a.GetVirtualSizeWithAncestors();
         } else {
             mod_fee = a.GetModifiedFee() / SATOSHI;
-            size = a.GetTxSize();
+            size = a.GetTxVirtualSize();
         }
     }
 };
diff --git a/src/txmempool.cpp b/src/txmempool.cpp
--- a/src/txmempool.cpp
+++ b/src/txmempool.cpp
@@ -1191,7 +1191,7 @@
         // mempool with feerate equal to txn which were removed with no block in
         // between.
         CFeeRate removed(it->GetModFeesWithDescendants(),
-                         it->GetSizeWithDescendants());
+                         it->GetVirtualSizeWithDescendants());
         removed += MEMPOOL_FULL_FEE_INCREMENT;
 
         trackPackageRemoved(removed);
diff --git a/src/validation.cpp b/src/validation.cpp
--- a/src/validation.cpp
+++ b/src/validation.cpp
@@ -684,6 +684,7 @@
         CTxMemPoolEntry entry(ptx, nFees, nAcceptTime, chainActive.Height(),
                               fSpendsCoinbase, nSigOpsCount, lp);
         unsigned int nSize = entry.GetTxSize();
+        unsigned int nVirtualSize = entry.GetTxVirtualSize();
 
         // Check that the transaction doesn't have an excessive number of
         // sigops, making it impossible to mine. Since the coinbase transaction
@@ -709,7 +710,7 @@
             pool.GetMinFee(
                     gArgs.GetArg("-maxmempool", DEFAULT_MAX_MEMPOOL_SIZE) *
                     1000000)
-                .GetFee(nSize);
+                .GetFee(nVirtualSize);
         if (!bypass_limits && mempoolRejectFee > Amount::zero() &&
             nModifiedFees < mempoolRejectFee) {
             return state.DoS(