diff --git a/src/app/Jobs/User/CreateJob.php b/src/app/Jobs/User/CreateJob.php
--- a/src/app/Jobs/User/CreateJob.php
+++ b/src/app/Jobs/User/CreateJob.php
@@ -12,10 +12,12 @@
  *   * The user is marked as deleted (`$user->isDeleted()`), or
  *   * the user is actually deleted (`$user->deleted_at`), or
  *   * the user is already marked as ready in LDAP (`$user->isLdapReady()`).
- *
  */
 class CreateJob extends UserJob
 {
+    /** @var int Enable waiting for a user record to exist */
+    protected $waitForUser = 5;
+
     /**
      * Execute the job.
      *
diff --git a/src/app/Jobs/User/UpdateJob.php b/src/app/Jobs/User/UpdateJob.php
--- a/src/app/Jobs/User/UpdateJob.php
+++ b/src/app/Jobs/User/UpdateJob.php
@@ -7,6 +7,9 @@
 
 class UpdateJob extends UserJob implements ShouldBeUniqueUntilProcessing
 {
+    /** @var int Enable waiting for a user record to exist */
+    protected $waitForUser = 5;
+
     /** @var int The number of seconds after which the job's unique lock will be released. */
     public $uniqueFor = 60;
 
@@ -28,6 +31,11 @@
             return;
         }
 
+        if ($user->trashed()) {
+            $this->delete();
+            return;
+        }
+
         if (\config('app.with_ldap') && $user->isLdapReady()) {
             \App\Backends\LDAP::updateUser($user);
         }
diff --git a/src/app/Jobs/UserJob.php b/src/app/Jobs/UserJob.php
--- a/src/app/Jobs/UserJob.php
+++ b/src/app/Jobs/UserJob.php
@@ -13,6 +13,9 @@
  */
 abstract class UserJob extends CommonJob
 {
+    /** @var int Enable waiting for a user record to exist. Delay time in seconds */
+    protected $waitForUser = 0;
+
     /**
      * The ID for the \App\User. This is the shortest globally unique identifier and saves Redis space
      * compared to a serialized version of the complete \App\User object.
@@ -60,8 +63,8 @@
         if (!$user) {
             // The record might not exist yet in case of a db replication environment
             // This will release the job and delay another attempt for 5 seconds
-            if ($this instanceof User\CreateJob) {
-                $this->release(5);
+            if ($this->waitForUser) {
+                $this->release($this->waitForUser);
                 return null;
             }
 
diff --git a/src/tests/Feature/Jobs/User/UpdateTest.php b/src/tests/Feature/Jobs/User/UpdateTest.php
--- a/src/tests/Feature/Jobs/User/UpdateTest.php
+++ b/src/tests/Feature/Jobs/User/UpdateTest.php
@@ -88,12 +88,21 @@
 
         $this->assertTrue(empty($ldap_user['alias']));
 
-        // Test non-existing user ID
+        // Test deleted user
+        $user->delete();
+        $job = new \App\Jobs\User\UpdateJob($user->id);
+        $job->handle();
+
+        $this->assertTrue($job->isDeleted());
+
+        // Test job failure (user unknown)
+        // The job will be released
+        $this->expectException(\Exception::class);
         $job = new \App\Jobs\User\UpdateJob(123);
         $job->handle();
 
-        $this->assertTrue($job->hasFailed());
-        $this->assertSame("User 123 could not be found in the database.", $job->failureMessage);
+        $this->assertTrue($job->isReleased());
+        $this->assertFalse($job->hasFailed());
 
         // TODO: Test IMAP, e.g. quota change
     }