diff --git a/src/net_processing.cpp b/src/net_processing.cpp
--- a/src/net_processing.cpp
+++ b/src/net_processing.cpp
@@ -4645,10 +4645,10 @@
             if (fSendTrickle && pto->m_tx_relay->fSendMempool) {
                 auto vtxinfo = g_mempool.infoAll();
                 pto->m_tx_relay->fSendMempool = false;
-                Amount filterrate = Amount::zero();
+                CFeeRate filterrate;
                 {
                     LOCK(pto->m_tx_relay->cs_feeFilter);
-                    filterrate = pto->m_tx_relay->minFeeFilter;
+                    filterrate = CFeeRate(pto->m_tx_relay->minFeeFilter);
                 }
 
                 LOCK(pto->m_tx_relay->cs_filter);
@@ -4657,8 +4657,9 @@
                     const TxId &txid = txinfo.tx->GetId();
                     CInv inv(MSG_TX, txid);
                     pto->m_tx_relay->setInventoryTxToSend.erase(txid);
-                    if (filterrate != Amount::zero() &&
-                        txinfo.feeRate.GetFeePerK() < filterrate) {
+                    // Don't send transactions that peers will not put into
+                    // their mempool
+                    if (txinfo.fee < filterrate.GetFee(txinfo.vsize)) {
                         continue;
                     }
                     if (pto->m_tx_relay->pfilter &&
@@ -4688,10 +4689,10 @@
                      it != pto->m_tx_relay->setInventoryTxToSend.end(); it++) {
                     vInvTx.push_back(it);
                 }
-                Amount filterrate = Amount::zero();
+                CFeeRate filterrate;
                 {
                     LOCK(pto->m_tx_relay->cs_feeFilter);
-                    filterrate = pto->m_tx_relay->minFeeFilter;
+                    filterrate = CFeeRate(pto->m_tx_relay->minFeeFilter);
                 }
                 // Topologically and fee-rate sort the inventory we send for
                 // privacy and priority reasons. A heap is used so that not all
@@ -4725,8 +4726,9 @@
                     if (!txinfo.tx) {
                         continue;
                     }
-                    if (filterrate != Amount::zero() &&
-                        txinfo.feeRate.GetFeePerK() < filterrate) {
+                    // Peer told you to not send transactions at that feerate?
+                    // Don't bother sending it.
+                    if (txinfo.fee < filterrate.GetFee(txinfo.vsize)) {
                         continue;
                     }
                     if (pto->m_tx_relay->pfilter &&
diff --git a/src/txmempool.h b/src/txmempool.h
--- a/src/txmempool.h
+++ b/src/txmempool.h
@@ -358,8 +358,11 @@
     /** Time the transaction entered the mempool. */
     std::chrono::seconds m_time;
 
-    /** Feerate of the transaction. */
-    CFeeRate feeRate;
+    /** Fee of the transaction. */
+    Amount fee;
+
+    /** Virtual size of the transaction. */
+    size_t vsize;
 
     /** The fee delta. */
     Amount nFeeDelta;
diff --git a/src/txmempool.cpp b/src/txmempool.cpp
--- a/src/txmempool.cpp
+++ b/src/txmempool.cpp
@@ -896,9 +896,8 @@
 
 static TxMempoolInfo
 GetInfo(CTxMemPool::indexed_transaction_set::const_iterator it) {
-    return TxMempoolInfo{it->GetSharedTx(), it->GetTime(),
-                         CFeeRate(it->GetFee(), it->GetTxSize()),
-                         it->GetModifiedFee() - it->GetFee()};
+    return TxMempoolInfo{it->GetSharedTx(), it->GetTime(), it->GetFee(),
+                         it->GetTxSize(), it->GetModifiedFee() - it->GetFee()};
 }
 
 std::vector<TxMempoolInfo> CTxMemPool::infoAll() const {
diff --git a/test/functional/p2p_feefilter.py b/test/functional/p2p_feefilter.py
--- a/test/functional/p2p_feefilter.py
+++ b/test/functional/p2p_feefilter.py
@@ -48,6 +48,13 @@
 class FeeFilterTest(BitcoinTestFramework):
     def set_test_params(self):
         self.num_nodes = 2
+        # We lower the various required feerates for this test
+        # to catch a corner-case where feefilter used to slightly undercut
+        # mempool and wallet feerate calculation based on GetFee
+        # rounding down 3 places, leading to stranded transactions.
+        # See issue #16499
+        self.extra_args = [["-minrelaytxfee=0.00000100",
+                            "-mintxfee=0.00000100"]] * self.num_nodes
 
     def skip_test_if_missing_module(self):
         self.skip_if_no_wallet()
@@ -61,25 +68,28 @@
 
         self.nodes[0].add_p2p_connection(TestP2PConn())
 
-        # Test that invs are received for all txs at feerate of 20 sat/byte
-        node1.settxfee(Decimal("0.00020000"))
+        # Test that invs are received by test connection for all txs at
+        # feerate of .2 sat/byte
+        node1.settxfee(Decimal("0.00000200"))
         txids = [node1.sendtoaddress(node1.getnewaddress(), 1)
                  for x in range(3)]
         assert allInvsMatch(txids, self.nodes[0].p2p)
         self.nodes[0].p2p.clear_invs()
 
-        # Set a filter of 15 sat/byte
-        self.nodes[0].p2p.send_and_ping(msg_feefilter(15000))
+        # Set a filter of .15 sat/byte on test connection
+        self.nodes[0].p2p.send_and_ping(msg_feefilter(150))
 
-        # Test that txs are still being received (paying 20 sat/byte)
+        # Test that txs are still being received by test connection
+        # (paying .15 sat/byte)
+        node1.settxfee(Decimal("0.00000150"))
         txids = [node1.sendtoaddress(node1.getnewaddress(), 1)
                  for x in range(3)]
         assert allInvsMatch(txids, self.nodes[0].p2p)
         self.nodes[0].p2p.clear_invs()
 
-        # Change tx fee rate to 10 sat/byte and test they are no longer
-        # received
-        node1.settxfee(Decimal("0.00010000"))
+        # Change tx fee rate to .1 sat/byte and test they are no longer received
+        # by the test connection
+        node1.settxfee(Decimal("0.00000100"))
         [node1.sendtoaddress(node1.getnewaddress(), 1) for x in range(3)]
         self.sync_mempools()  # must be sure node 0 has received all txs