diff -u b/core/lib/Drupal/Core/KeyValueStore/DatabaseStorageExpire.php b/core/lib/Drupal/Core/KeyValueStore/DatabaseStorageExpire.php
--- b/core/lib/Drupal/Core/KeyValueStore/DatabaseStorageExpire.php
+++ b/core/lib/Drupal/Core/KeyValueStore/DatabaseStorageExpire.php
@@ -138,16 +138,6 @@
   }
 
   /**
-   * Implements Drupal\Core\KeyValueStore\KeyValueStoreInterface::deleteAll().
-   */
-  public function deleteAll() {
-    $this->garbageCollection();
-    $this->connection->delete($this->table)
-      ->condition('collection', $this->collection)
-      ->execute();
-  }
-
-  /**
    * Delete expired items.
    */
   protected function garbageCollection() {
diff -u b/core/modules/user/lib/Drupal/user/KeyValueStoreWithOwner.php b/core/modules/user/lib/Drupal/user/KeyValueStoreWithOwner.php
--- b/core/modules/user/lib/Drupal/user/KeyValueStoreWithOwner.php
+++ b/core/modules/user/lib/Drupal/user/KeyValueStoreWithOwner.php
@@ -86,10 +86,11 @@
    * Deletes the value of the default key.
    */
   function delete($key) {
-    // If a write is in progress, we will wait until it finishes then nuke it
-    // immediately.
-    while (!$this->lockBackend->acquire($key) && time() < REQUEST_TIME + 60) {
+    if (!$this->lockBackend->acquire($key)) {
       $this->lockBackend->wait($key);
+      if (!$this->lockBackend->acquire($key)) {
+        throw new KeyValueStoreWithOwnerException("Couldn't acquire lock");
+      }
     }
     $this->storage->delete($key);
     $this->lockBackend->release($key);
diff -u b/core/modules/user/lib/Drupal/user/Tests/TempStoreDatabaseTest.php b/core/modules/user/lib/Drupal/user/Tests/TempStoreDatabaseTest.php
--- b/core/modules/user/lib/Drupal/user/Tests/TempStoreDatabaseTest.php
+++ b/core/modules/user/lib/Drupal/user/Tests/TempStoreDatabaseTest.php
@@ -49,6 +49,7 @@
     db_create_table('semaphore', $schema['semaphore']);
     db_create_table('key_value_expire', $schema['key_value_expire']);
     $this->storeFactory = new KeyValueStoreWithOwnerFactory(Database::getConnection(), new DatabaseLockBackend());
+    $this->collection = $this->randomName();
 
     // Create two users and two objects for testing.
     for ($i = 0; $i <= 3; $i++) {
@@ -83,11 +84,8 @@
   public function testUserTempStore() {
     $key = $this->randomName();
     // First test that only one setIfNotExists succeeds.
-    $namespace = $this->randomName();
     for ($i = 0; $i <= 1; $i++) {
-      $GLOBALS['user']->uid = $this->users[$i];
-      // This relies on the logged user uid!!
-      $store = $this->storeFactory->get($namespace);
+      $store = $this->getStorePerUid($this->users[$i]);
       // Setting twice results only in the first succeeding.
       $this->assertEqual(!$i, $store->setIfNotExists($key, $this->objects[$i]));
       $this->assertEqual($this->users[0], $store->getOwner($key));
@@ -103,10 +101,30 @@
     $store->set($key, $this->objects[2]);
     $this->assertIdenticalObject($this->objects[2], $store->get($key));
     // But another can't.
-    $GLOBALS['user']->uid = $this->users[2];
-    $store = $this->storeFactory->get($namespace);
+    $store = $this->getStorePerUid($this->users[2]);
     $store->set($key, $this->objects[3]);
     $this->assertIdenticalObject($this->objects[2], $store->get($key));
+    // Now manually expire the item (this is not exposed by the API) and then
+    // assert it is no longer accessible.
+    db_update('key_value_expire')
+      ->fields(array('expire' => REQUEST_TIME - 1))
+      ->condition('collection', $this->collection)
+      ->condition('name', $key)
+      ->execute();
+    $this->assertFalse($store->get($key));
+  }
+
+  /**
+   * Returns a KeyValueStoreWithOwner belonging to the passed in user.
+   *
+   * @param $uid
+   *   A user ID.
+   * @return Drupal\user\KeyValueStoreWithOwner
+   */
+  protected function getStorePerUid($uid) {
+    $GLOBALS['user']->uid = $uid;
+    // This relies on the logged user uid!!
+    return $this->storeFactory->get($this->collection);
   }
 
   protected function assertIdenticalObject($object1, $object2) {
only in patch2:
unchanged:
--- /dev/null
+++ b/core/modules/user/lib/Drupal/user/KeyValueStoreWithOwnerException.php
@@ -0,0 +1,14 @@
+<?php
+
+/**
+ * @file
+ * Contains Drupal\Core\KeyValueStore\KeyValueStoreDefaultException.
+ */
+
+namespace Drupal\user;
+
+/**
+ * Exception thrown when KeyValueStoreWithOwner can not acquire a lock.
+ */
+class KeyValueStoreWithOwnerException extends \Exception {}
+