diff --git a/src/app/Jobs/CommonJob.php b/src/app/Jobs/CommonJob.php
--- a/src/app/Jobs/CommonJob.php
+++ b/src/app/Jobs/CommonJob.php
@@ -30,6 +30,13 @@
     public $failureMessage;
 
     /**
+     * The job released state.
+     *
+     * @var bool
+     */
+    protected $isReleased = false;
+
+    /**
      * The number of tries for this Job.
      *
      * @var int
@@ -70,4 +77,31 @@
     {
         return $this->failureMessage !== null;
     }
+
+    /**
+     * Release the job back into the queue.
+     *
+     * @param int $delay Time in seconds
+     * @return void
+     */
+    public function release($delay = 0)
+    {
+        // We need this for testing purposes
+        $this->isReleased = true;
+
+        // @phpstan-ignore-next-line
+        if ($this->job) {
+            $this->job->release($delay);
+        }
+    }
+
+    /**
+     * Check if the job was released
+     *
+     * @return bool
+     */
+    public function isReleased(): bool
+    {
+        return $this->isReleased;
+    }
 }
diff --git a/src/app/Jobs/Domain/CreateJob.php b/src/app/Jobs/Domain/CreateJob.php
--- a/src/app/Jobs/Domain/CreateJob.php
+++ b/src/app/Jobs/Domain/CreateJob.php
@@ -15,6 +15,10 @@
     {
         $domain = $this->getDomain();
 
+        if (!$domain) {
+            return;
+        }
+
         if (!$domain->isLdapReady()) {
             \App\Backends\LDAP::createDomain($domain);
 
diff --git a/src/app/Jobs/Domain/DeleteJob.php b/src/app/Jobs/Domain/DeleteJob.php
--- a/src/app/Jobs/Domain/DeleteJob.php
+++ b/src/app/Jobs/Domain/DeleteJob.php
@@ -15,6 +15,10 @@
     {
         $domain = $this->getDomain();
 
+        if (!$domain) {
+            return;
+        }
+
         // sanity checks
         if ($domain->isDeleted()) {
             $this->fail(new \Exception("Domain {$this->domainId} is already marked as deleted."));
diff --git a/src/app/Jobs/Domain/UpdateJob.php b/src/app/Jobs/Domain/UpdateJob.php
--- a/src/app/Jobs/Domain/UpdateJob.php
+++ b/src/app/Jobs/Domain/UpdateJob.php
@@ -15,6 +15,10 @@
     {
         $domain = $this->getDomain();
 
+        if (!$domain) {
+            return;
+        }
+
         if (!$domain->isLdapReady()) {
             $this->delete();
             return;
diff --git a/src/app/Jobs/Domain/VerifyJob.php b/src/app/Jobs/Domain/VerifyJob.php
--- a/src/app/Jobs/Domain/VerifyJob.php
+++ b/src/app/Jobs/Domain/VerifyJob.php
@@ -15,6 +15,10 @@
     {
         $domain = $this->getDomain();
 
+        if (!$domain) {
+            return;
+        }
+
         $domain->verify();
     }
 }
diff --git a/src/app/Jobs/DomainJob.php b/src/app/Jobs/DomainJob.php
--- a/src/app/Jobs/DomainJob.php
+++ b/src/app/Jobs/DomainJob.php
@@ -58,6 +58,13 @@
         $domain = \App\Domain::withTrashed()->find($this->domainId);
 
         if (!$domain) {
+            // 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 Domain\CreateJob) {
+                $this->release(5);
+                return null;
+            }
+
             $this->fail(new \Exception("Domain {$this->domainId} could not be found in the database."));
         }
 
diff --git a/src/app/Jobs/Group/CreateJob.php b/src/app/Jobs/Group/CreateJob.php
--- a/src/app/Jobs/Group/CreateJob.php
+++ b/src/app/Jobs/Group/CreateJob.php
@@ -15,6 +15,10 @@
     {
         $group = $this->getGroup();
 
+        if (!$group) {
+            return;
+        }
+
         if (!$group->isLdapReady()) {
             \App\Backends\LDAP::createGroup($group);
 
diff --git a/src/app/Jobs/Group/DeleteJob.php b/src/app/Jobs/Group/DeleteJob.php
--- a/src/app/Jobs/Group/DeleteJob.php
+++ b/src/app/Jobs/Group/DeleteJob.php
@@ -15,6 +15,10 @@
     {
         $group = $this->getGroup();
 
+        if (!$group) {
+            return;
+        }
+
         // sanity checks
         if ($group->isDeleted()) {
             $this->fail(new \Exception("Group {$this->groupId} is already marked as deleted."));
diff --git a/src/app/Jobs/Group/UpdateJob.php b/src/app/Jobs/Group/UpdateJob.php
--- a/src/app/Jobs/Group/UpdateJob.php
+++ b/src/app/Jobs/Group/UpdateJob.php
@@ -15,6 +15,10 @@
     {
         $group = $this->getGroup();
 
+        if (!$group) {
+            return;
+        }
+
         if (!$group->isLdapReady()) {
             $this->delete();
             return;
diff --git a/src/app/Jobs/GroupJob.php b/src/app/Jobs/GroupJob.php
--- a/src/app/Jobs/GroupJob.php
+++ b/src/app/Jobs/GroupJob.php
@@ -58,6 +58,13 @@
         $group = \App\Group::withTrashed()->find($this->groupId);
 
         if (!$group) {
+            // 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 Group\CreateJob) {
+                $this->release(5);
+                return null;
+            }
+
             $this->fail(new \Exception("Group {$this->groupId} could not be found in the database."));
         }
 
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
@@ -15,6 +15,10 @@
     {
         $user = $this->getUser();
 
+        if (!$user) {
+            return;
+        }
+
         if (!$user->isLdapReady()) {
             $this->delete();
             return;
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
@@ -58,6 +58,13 @@
         $user = \App\User::withTrashed()->find($this->userId);
 
         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);
+                return null;
+            }
+
             $this->fail(new \Exception("User {$this->userId} could not be found in the database."));
         }
 
diff --git a/src/tests/Feature/Jobs/DomainCreateTest.php b/src/tests/Feature/Jobs/DomainCreateTest.php
--- a/src/tests/Feature/Jobs/DomainCreateTest.php
+++ b/src/tests/Feature/Jobs/DomainCreateTest.php
@@ -63,5 +63,12 @@
                     $domainNamespace === $domain->namespace;
             }
         );
+
+        // Test job releasing on unknown identifier
+        $job = new \App\Jobs\Domain\CreateJob(123);
+        $job->handle();
+
+        $this->assertTrue($job->isReleased());
+        $this->assertFalse($job->hasFailed());
     }
 }
diff --git a/src/tests/Feature/Jobs/DomainVerifyTest.php b/src/tests/Feature/Jobs/DomainVerifyTest.php
--- a/src/tests/Feature/Jobs/DomainVerifyTest.php
+++ b/src/tests/Feature/Jobs/DomainVerifyTest.php
@@ -47,6 +47,13 @@
         $job->handle();
 
         $this->assertTrue($domain->fresh()->isVerified());
+
+        // Test non-existing domain ID
+        $job = new \App\Jobs\Domain\VerifyJob(123);
+        $job->handle();
+
+        $this->assertTrue($job->hasFailed());
+        $this->assertSame("Domain 123 could not be found in the database.", $job->failureMessage);
     }
 
     /**
diff --git a/src/tests/Feature/Jobs/Group/CreateTest.php b/src/tests/Feature/Jobs/Group/CreateTest.php
--- a/src/tests/Feature/Jobs/Group/CreateTest.php
+++ b/src/tests/Feature/Jobs/Group/CreateTest.php
@@ -39,5 +39,12 @@
         $job->handle();
 
         $this->assertTrue($group->fresh()->isLdapReady());
+
+        // Test non-existing group ID
+        $job = new \App\Jobs\Group\CreateJob(123);
+        $job->handle();
+
+        $this->assertTrue($job->isReleased());
+        $this->assertFalse($job->hasFailed());
     }
 }
diff --git a/src/tests/Feature/Jobs/Group/DeleteTest.php b/src/tests/Feature/Jobs/Group/DeleteTest.php
--- a/src/tests/Feature/Jobs/Group/DeleteTest.php
+++ b/src/tests/Feature/Jobs/Group/DeleteTest.php
@@ -49,5 +49,12 @@
 
         $this->assertFalse($group->isLdapReady());
         $this->assertTrue($group->isDeleted());
+
+        // Test non-existing group ID
+        $job = new \App\Jobs\Group\DeleteJob(123);
+        $job->handle();
+
+        $this->assertTrue($job->hasFailed());
+        $this->assertSame("Group 123 could not be found in the database.", $job->failureMessage);
     }
 }
diff --git a/src/tests/Feature/Jobs/Group/UpdateTest.php b/src/tests/Feature/Jobs/Group/UpdateTest.php
--- a/src/tests/Feature/Jobs/Group/UpdateTest.php
+++ b/src/tests/Feature/Jobs/Group/UpdateTest.php
@@ -38,5 +38,12 @@
 
         // TODO: Test if group properties (members) actually changed in LDAP
         $this->assertTrue(true);
+
+        // Test non-existing group ID
+        $job = new \App\Jobs\Group\UpdateJob(123);
+        $job->handle();
+
+        $this->assertTrue($job->hasFailed());
+        $this->assertSame("Group 123 could not be found in the database.", $job->failureMessage);
     }
 }
diff --git a/src/tests/Feature/Jobs/UserCreateTest.php b/src/tests/Feature/Jobs/UserCreateTest.php
--- a/src/tests/Feature/Jobs/UserCreateTest.php
+++ b/src/tests/Feature/Jobs/UserCreateTest.php
@@ -72,7 +72,7 @@
         $job = new \App\Jobs\User\CreateJob(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());
     }
 }
diff --git a/src/tests/Feature/Jobs/UserUpdateTest.php b/src/tests/Feature/Jobs/UserUpdateTest.php
--- a/src/tests/Feature/Jobs/UserUpdateTest.php
+++ b/src/tests/Feature/Jobs/UserUpdateTest.php
@@ -83,5 +83,12 @@
         $ldap_user = LDAP::getUser('new-job-user@' . \config('app.domain'));
 
         $this->assertTrue(empty($ldap_user['alias']));
+
+        // Test non-existing user ID
+        $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);
     }
 }
diff --git a/src/tests/Feature/Jobs/UserVerifyTest.php b/src/tests/Feature/Jobs/UserVerifyTest.php
--- a/src/tests/Feature/Jobs/UserVerifyTest.php
+++ b/src/tests/Feature/Jobs/UserVerifyTest.php
@@ -41,6 +41,14 @@
     {
         Queue::fake();
 
+        // Test non-existing user ID
+        $job = new \App\Jobs\User\VerifyJob(123);
+        $job->handle();
+
+        $this->assertTrue($job->hasFailed());
+        $this->assertSame("User 123 could not be found in the database.", $job->failureMessage);
+
+        // Test existing user
         $user = $this->getTestUser('ned@kolab.org');
 
         if ($user->isImapReady()) {