diff --git a/pw_kvs/key_value_store.cc b/pw_kvs/key_value_store.cc
index b9beed2..5d7ffd8 100644
--- a/pw_kvs/key_value_store.cc
+++ b/pw_kvs/key_value_store.cc
@@ -512,7 +512,7 @@
   TRY(FindOrRecoverSectorWithSpace(
       &sector, Entry::size(partition_.alignment_bytes(), key, value)));
   DBG("Writing new entry; found sector: %zu", SectorIndex(sector));
-  TRY(AppendEntry(sector, &key_descriptor, key, value));
+  TRY(AppendEntry(sector, &key_descriptor, key, value, KeyDescriptor::kValid));
 
   // Only add the entry when we are certain the write succeeded.
   key_descriptors_.push_back(key_descriptor);
@@ -552,7 +552,8 @@
   // Find a new sector for the entry and write it to the new location.
   SectorDescriptor* new_sector;
   TRY(FindSectorWithSpace(&new_sector, header.size(), old_sector, true));
-  TRY(AppendEntry(new_sector, &key_descriptor, key, as_bytes(value)));
+  TRY(AppendEntry(
+      new_sector, &key_descriptor, key, as_bytes(value), key_descriptor.state));
 
   // Do the valid bytes accounting for the sector the entry was relocated out
   // of.
diff --git a/pw_kvs/key_value_store_map_test.cc b/pw_kvs/key_value_store_map_test.cc
index 7c3dda5..c976db2 100644
--- a/pw_kvs/key_value_store_map_test.cc
+++ b/pw_kvs/key_value_store_map_test.cc
@@ -12,10 +12,13 @@
 // License for the specific language governing permissions and limitations under
 // the License.
 
+#include <cstdlib>
 #include <random>
+#include <set>
 #include <string>
 #include <string_view>
 #include <unordered_map>
+#include <unordered_set>
 
 #define DUMP_KVS_CONTENTS 0
 
@@ -27,6 +30,7 @@
 #include "pw_kvs/crc16_checksum.h"
 #include "pw_kvs/in_memory_fake_flash.h"
 #include "pw_kvs/key_value_store.h"
+#include "pw_log/log.h"
 #include "pw_span/span.h"
 
 namespace pw::kvs {
@@ -48,6 +52,18 @@
   size_t partition_alignment;
 };
 
+template <typename T>
+std::set<T> difference(const std::set<T> lhs, const std::set<T> rhs) {
+  std::set<T> diff;
+  std::set_difference(lhs.begin(),
+                      lhs.end(),
+                      rhs.begin(),
+                      rhs.end(),
+                      std::inserter(diff, diff.begin()));
+
+  return diff;
+}
+
 template <const TestParameters& kParams>
 class KvsTester {
  public:
@@ -69,43 +85,9 @@
     }
   }
 
-  ~KvsTester() {
-#if DUMP_KVS_CONTENTS
-    std::cout << "/==============================================\\\n";
-    std::cout << "KVS EXPECTED CONTENTS\n";
-    std::cout << "------------------------------------------------\n";
-    std::cout << "Entries: " << map_.size() << '\n';
-    std::cout << "------------------------------------------------\n";
-    for (const auto& [key, value] : map_) {
-      std::cout << key << " = " << value << '\n';
-    }
-    std::cout << "\\===============================================/\n";
-#endif  // DUMP_KVS_CONTENTS
+  ~KvsTester() { CompareContents(); }
 
-    EXPECT_EQ(map_.size(), kvs_.size());
-
-    size_t count = 0;
-
-    for (auto& item : kvs_) {
-      count += 1;
-
-      auto map_entry = map_.find(std::string(item.key()));
-      EXPECT_NE(map_entry, map_.end());
-
-      if (map_entry != map_.end()) {
-        EXPECT_EQ(map_entry->first, item.key());
-
-        char value[kMaxValueLength + 1] = {};
-        EXPECT_EQ(Status::OK,
-                  item.Get(as_writable_bytes(span(value))).status());
-        EXPECT_EQ(map_entry->second, std::string(value));
-      }
-    }
-
-    EXPECT_EQ(count, map_.size());
-  }
-
-  void TestRandomValidInputs(int iterations) {
+  void Test_RandomValidInputs(int iterations) {
     std::mt19937 random(6006411);
     std::uniform_int_distribution<unsigned> distro;
     auto random_int = [&] { return distro(random); };
@@ -142,7 +124,7 @@
     }
   }
 
-  void TestPut() {
+  void Test_Put() {
     Put("base_key", "base_value");
     for (int i = 0; i < 100; ++i) {
       Put("other_key", std::to_string(i));
@@ -152,10 +134,86 @@
     }
   }
 
+  void Test_PutAndDelete_RelocateDeletedEntriesShouldStayDeleted() {
+    for (int i = 0; i < 100; ++i) {
+      std::string str = "key_" + std::to_string(i);
+      Put(str, std::string(kMaxValueLength, '?'));
+      Delete(str);
+    }
+  }
+
  private:
+  void CompareContents() {
+#if DUMP_KVS_CONTENTS
+    std::set<std::string> map_keys, kvs_keys;
+
+    std::cout << "/==============================================\\\n";
+    std::cout << "KVS EXPECTED CONTENTS\n";
+    std::cout << "------------------------------------------------\n";
+    std::cout << "Entries: " << map_.size() << '\n';
+    std::cout << "------------------------------------------------\n";
+    for (const auto& [key, value] : map_) {
+      std::cout << key << " = " << value << '\n';
+      map_keys.insert(key);
+    }
+    std::cout << "\\===============================================/\n";
+
+    std::cout << "/==============================================\\\n";
+    std::cout << "KVS ACTUAL CONTENTS\n";
+    std::cout << "------------------------------------------------\n";
+    std::cout << "Entries: " << kvs_.size() << '\n';
+    std::cout << "------------------------------------------------\n";
+    for (const auto& item : kvs_) {
+      std::cout << item.key() << " = " << item.ValueSize().size() << " B\n";
+      kvs_keys.insert(std::string(item.key()));
+    }
+    std::cout << "\\===============================================/\n";
+
+    auto missing_from_kvs = difference(map_keys, kvs_keys);
+
+    if (!missing_from_kvs.empty()) {
+      std::cout << "MISSING FROM KVS: " << missing_from_kvs.size() << '\n';
+      for (auto& key : missing_from_kvs) {
+        std::cout << key << '\n';
+      }
+    }
+
+    auto missing_from_map = difference(kvs_keys, map_keys);
+    if (!missing_from_map.empty()) {
+      std::cout << "MISSING FROM MAP: " << missing_from_map.size() << '\n';
+      for (auto& key : missing_from_map) {
+        std::cout << key << '\n';
+      }
+    }
+#endif  // DUMP_KVS_CONTENTS
+
+    EXPECT_EQ(map_.size(), kvs_.size());
+
+    size_t count = 0;
+
+    for (auto& item : kvs_) {
+      count += 1;
+
+      auto map_entry = map_.find(std::string(item.key()));
+      if (map_entry == map_.end()) {
+        PW_LOG_CRITICAL("Entry %s missing from map", item.key().data());
+      } else if (map_entry != map_.end()) {
+        EXPECT_EQ(map_entry->first, item.key());
+
+        char value[kMaxValueLength + 1] = {};
+        EXPECT_EQ(Status::OK,
+                  item.Get(as_writable_bytes(span(value))).status());
+        EXPECT_EQ(map_entry->second, std::string(value));
+      }
+    }
+
+    EXPECT_EQ(count, map_.size());
+  }
+
   // Adds a key to the KVS, if there is room for it.
   void Put(const std::string& key, const std::string& value) {
-    ASSERT_LE(value.size(), kMaxValueLength);
+    StartOperation("Put", key);
+    EXPECT_LE(value.size(), kMaxValueLength);
 
     Status result = kvs_.Put(key, as_bytes(span(value)));
 
@@ -163,24 +221,66 @@
       EXPECT_EQ(Status::INVALID_ARGUMENT, result);
     } else if (map_.size() == KeyValueStore::kMaxEntries) {
       EXPECT_EQ(Status::RESOURCE_EXHAUSTED, result);
-    } else {
-      ASSERT_EQ(Status::OK, result);
+    } else if (result == Status::RESOURCE_EXHAUSTED) {
+      EXPECT_FALSE(map_.empty());
+    } else if (result.ok()) {
       map_[key] = value;
+      deleted_.erase(key);
+    } else {
+      PW_LOG_CRITICAL("Put: unhandled result %s", result.str());
+      std::abort();
+    }
+
+    FinishOperation("Put", result, key);
+
+    if (kvs_.size() != map_.size()) {
+      PW_LOG_CRITICAL("Put: size mismatch; expected %zu, actual %zu",
+                      map_.size(),
+                      kvs_.size());
+      std::abort();
     }
   }
 
   // Deletes a key from the KVS if it is present.
   void Delete(const std::string& key) {
+    StartOperation("Delete", key);
+
     Status result = kvs_.Delete(key);
 
     if (key.empty() || key.size() >= KeyValueStore::kMaxKeyLength) {
       EXPECT_EQ(Status::INVALID_ARGUMENT, result);
     } else if (map_.count(key) == 0) {
       EXPECT_EQ(Status::NOT_FOUND, result);
-    } else {
-      ASSERT_EQ(Status::OK, result);
+    } else if (result.ok()) {
       map_.erase(key);
+
+      if (deleted_.count(key) > 0u) {
+        PW_LOG_CRITICAL("Deleted key that was already deleted %s", key.c_str());
+        std::abort();
+      }
+
+      deleted_.insert(key);
+    } else {
+      PW_LOG_CRITICAL("Delete: unhandled result %s", result.str());
+      std::abort();
     }
+    FinishOperation("Delete", result, key);
+  }
+
+  void StartOperation(const std::string& operation, const std::string& key) {
+    count_ += 1;
+    PW_LOG_CRITICAL(
+        "[%3u] START %s for '%s'", count_, operation.c_str(), key.c_str());
+  }
+
+  void FinishOperation(const std::string& operation,
+                       Status result,
+                       const std::string& key) {
+    PW_LOG_CRITICAL("[%3u] FINISH %s <%s> for '%s'",
+                    count_,
+                    operation.c_str(),
+                    result.str(),
+                    key.c_str());
   }
 
   bool empty() const { return map_.empty(); }
@@ -196,6 +296,8 @@
 
   KeyValueStore kvs_;
   std::unordered_map<std::string, std::string> map_;
+  std::unordered_set<std::string> deleted_;
+  unsigned count_ = 0;
 };
 
 template <const TestParameters& kParams>
@@ -204,6 +306,9 @@
         InMemoryFakeFlash<kParams.sector_size, kParams.sector_count>(
             kParams.sector_alignment);
 
+#define _TEST(fixture, test, ...) \
+  TEST_F(fixture, test) { tester_.Test_##test(__VA_ARGS__); }
+
 // Defines a test fixture that runs all tests against a flash with the specified
 // parameters.
 #define RUN_TESTS_WITH_PARAMETERS(name, ...)                                \
@@ -215,11 +320,9 @@
   };                                                                        \
                                                                             \
   /* Run each test defined in the KvsTester class with these parameters. */ \
-                                                                            \
-  TEST_F(name, Put) { tester_.TestPut(); }                                  \
-  TEST_F(name, DISABLED_RandomValidInputs) { /* TODO: Get this passing! */  \
-    tester_.TestRandomValidInputs(1000);                                    \
-  }                                                                         \
+  _TEST(name, Put);                                                         \
+  _TEST(name, PutAndDelete_RelocateDeletedEntriesShouldStayDeleted);        \
+  _TEST(name, RandomValidInputs, 1000)                                      \
   static_assert(true, "Don't forget a semicolon!")
 
 RUN_TESTS_WITH_PARAMETERS(Basic,
diff --git a/pw_kvs/public/pw_kvs/key_value_store.h b/pw_kvs/public/pw_kvs/key_value_store.h
index bb3d029..749af8d 100644
--- a/pw_kvs/public/pw_kvs/key_value_store.h
+++ b/pw_kvs/public/pw_kvs/key_value_store.h
@@ -321,7 +321,7 @@
                      KeyDescriptor* key_descriptor,
                      std::string_view key,
                      span<const std::byte> value,
-                     KeyDescriptor::State new_state = KeyDescriptor::kValid);
+                     KeyDescriptor::State new_state);
 
   bool AddressInSector(const SectorDescriptor& sector, Address address) const {
     const Address sector_base = SectorBaseAddress(&sector);