diff --git a/src/app/Backends/IMAP.php b/src/app/Backends/IMAP.php
--- a/src/app/Backends/IMAP.php
+++ b/src/app/Backends/IMAP.php
@@ -52,7 +52,8 @@
         //        should we consider using it in ACL instead of the name?
         //        Also we need to decide what to do and configure IMAP appropriately,
         //        right now groups in ACL does not work for me at all.
-        \App\Jobs\IMAP\AclCleanupJob::dispatch($group->name, $domainName);
+        // Commented out in favor of a nightly cleanup job, for performance reasons
+        // \App\Jobs\IMAP\AclCleanupJob::dispatch($group->name, $domainName);
 
         return true;
     }
@@ -169,7 +170,8 @@
         $imap->closeConnection();
 
         // Cleanup ACL
-        \App\Jobs\IMAP\AclCleanupJob::dispatch($user->email);
+        // Commented out in favor of a nightly cleanup job, for performance reasons
+        // \App\Jobs\IMAP\AclCleanupJob::dispatch($user->email);
 
         return $result;
     }
@@ -515,6 +517,7 @@
         $callback = function ($folder) use ($imap, $ident) {
             $acl = $imap->getACL($folder);
             if (is_array($acl) && isset($acl[$ident])) {
+                \Log::info("Cleanup: Removing {$ident} from ACL on {$folder}");
                 $imap->deleteACL($folder, $ident);
             }
         };
@@ -540,6 +543,70 @@
         $imap->closeConnection();
     }
 
+    /**
+     * Remove ACL entries pointing to non-existent users/groups, for a specified domain
+     *
+     * @param string $domain  Domain namespace
+     * @param bool   $dry_run Output ACL entries to delete, but do not delete
+     */
+    public static function aclCleanupDomain(string $domain, bool $dry_run = false): void
+    {
+        $config = self::getConfig();
+        $imap = self::initIMAP($config);
+
+        // Collect available (existing) users/groups
+        // FIXME: Should we limit this to the requested domain or account?
+        // FIXME: For groups should we use name or email?
+        $idents = User::pluck('email')
+            // ->concat(Group::pluck('name'))
+            ->concat(['anyone', 'anonymous', $config['user']])
+            ->all();
+
+        $callback = function ($folder) use ($imap, $idents, $dry_run) {
+            $acl = $imap->getACL($folder);
+            if (is_array($acl)) {
+                $owner = null;
+                if (preg_match('|^user/([^/@]+).*@([^@/]+)$|', $folder, $m)) {
+                    $owner = $m[1] . '@' . $m[2];
+                }
+                foreach (array_keys($acl) as $key) {
+                    if ($owner && $key === $owner) {
+                        // Don't even try to remove the folder's owner entry
+                        continue;
+                    }
+                    if (!in_array($key, $idents)) {
+                        if ($dry_run) {
+                            echo "{$folder} {$key} {$acl[$key]}\n";
+                        } else {
+                            \Log::info("Cleanup: Removing {$key} from ACL on {$folder}");
+                            $imap->deleteACL($folder, $key);
+                        }
+                    }
+                }
+            }
+        };
+
+        $folders = $imap->listMailboxes('', "user/*@{$domain}");
+
+        if (!is_array($folders)) {
+            $imap->closeConnection();
+            throw new \Exception("Failed to get IMAP folders");
+        }
+
+        array_walk($folders, $callback);
+
+        $folders = $imap->listMailboxes('', "shared/*@{$domain}");
+
+        if (!is_array($folders)) {
+            $imap->closeConnection();
+            throw new \Exception("Failed to get IMAP folders");
+        }
+
+        array_walk($folders, $callback);
+
+        $imap->closeConnection();
+    }
+
     /**
      * Create a folder and set some default properties
      *
diff --git a/src/app/Console/Commands/ImapCleanupCommand.php b/src/app/Console/Commands/ImapCleanupCommand.php
new file mode 100644
--- /dev/null
+++ b/src/app/Console/Commands/ImapCleanupCommand.php
@@ -0,0 +1,52 @@
+<?php
+
+namespace App\Console\Commands;
+
+use App\Console\Command;
+use App\Domain;
+
+class ImapCleanupCommand extends Command
+{
+    /**
+     * The name and signature of the console command.
+     *
+     * @var string
+     */
+    protected $signature = 'imap:cleanup {domain?} {--dry-run}';
+
+    /**
+     * The console command description.
+     *
+     * @var string
+     */
+    protected $description = "Cleanup IMAP ACL leftowers";
+
+    /**
+     * Execute the console command.
+     *
+     * @return mixed
+     */
+    public function handle()
+    {
+        $domain = $this->argument('domain');
+        $dry_run = $this->option('dry-run');
+
+        if (!$domain) {
+            foreach (Domain::pluck('namespace')->all() as $domain) {
+                // TODO: Execute this in parallel/background?
+                \App\Backends\IMAP::aclCleanupDomain($domain, $dry_run);
+            }
+
+            return;
+        }
+
+        $domain = $this->getDomain($domain);
+
+        if (!$domain) {
+            $this->error("Domain not found.");
+            return 1;
+        }
+
+        \App\Backends\IMAP::aclCleanupDomain($domain->namespace, $dry_run);
+    }
+}
diff --git a/src/app/Console/Kernel.php b/src/app/Console/Kernel.php
--- a/src/app/Console/Kernel.php
+++ b/src/app/Console/Kernel.php
@@ -26,6 +26,9 @@
         // This removes deleted storage files/file chunks from the filesystem
         $schedule->command('fs:expunge')->hourly();
 
+        // This cleans up IMAP ACL for deleted users/etc.
+        //$schedule->command('imap:cleanup')->dailyAt('03:00');
+
         // This notifies users about an end of the trial period
         $schedule->command('wallet:trial-end')->dailyAt('07:00');
 
diff --git a/src/tests/Feature/Backends/IMAPTest.php b/src/tests/Feature/Backends/IMAPTest.php
--- a/src/tests/Feature/Backends/IMAPTest.php
+++ b/src/tests/Feature/Backends/IMAPTest.php
@@ -83,6 +83,55 @@
 */
     }
 
+    /**
+     * Test aclCleanupDomain()
+     *
+     * @group imap
+     * @group ldap
+     */
+    public function testAclCleanupDomain(): void
+    {
+        $this->user = $user = $this->getTestUser('test-' . time() . '@kolab.org');
+        $this->group = $group = $this->getTestGroup('test-group-' . time() . '@kolab.org');
+
+        // SETACL requires that the user/group exists in LDAP
+        LDAP::createUser($user);
+        // LDAP::createGroup($group);
+
+        // First, set some ACLs that we'll expect to be removed later
+        $imap = $this->getImap();
+
+        $this->assertTrue($imap->setACL('user/john@kolab.org', 'anyone', 'lrs'));
+        $this->assertTrue($imap->setACL('user/john@kolab.org', 'jack@kolab.org', 'lrs'));
+        $this->assertTrue($imap->setACL('user/john@kolab.org', $user->email, 'lrs'));
+        $this->assertTrue($imap->setACL('shared/Resources/Conference Room #1@kolab.org', 'anyone', 'lrs'));
+        $this->assertTrue($imap->setACL('shared/Resources/Conference Room #1@kolab.org', 'jack@kolab.org', 'lrs'));
+        $this->assertTrue($imap->setACL('shared/Resources/Conference Room #1@kolab.org', $user->email, 'lrs'));
+/*
+        $this->assertTrue($imap->setACL('user/john@kolab.org', $group->name, 'lrs'));
+        $this->assertTrue($imap->setACL('shared/Resources/Conference Room #1@kolab.org', $group->name, 'lrs'));
+
+        $group->delete();
+*/
+        $user->delete();
+
+        // Cleanup ACL for the domain
+        IMAP::aclCleanupDomain('kolab.org');
+
+        $acl = $imap->getACL('user/john@kolab.org');
+        $this->assertTrue(is_array($acl) && !isset($acl[$user->email]));
+        $this->assertTrue(is_array($acl) && isset($acl['jack@kolab.org']));
+        $this->assertTrue(is_array($acl) && isset($acl['anyone']));
+        $this->assertTrue(is_array($acl) && isset($acl['john@kolab.org']));
+        // $this->assertTrue(is_array($acl) && !isset($acl[$group->name]));
+
+        $acl = $imap->getACL('shared/Resources/Conference Room #1@kolab.org');
+        $this->assertTrue(is_array($acl) && !isset($acl[$user->email]));
+        $this->assertTrue(is_array($acl) && isset($acl['jack@kolab.org']));
+        $this->assertTrue(is_array($acl) && isset($acl['anyone']));
+        // $this->assertTrue(is_array($acl) && !isset($acl[$group->name]));
+    }
+
     /**
      * Test creating/updating/deleting an IMAP account
      *