diff --git a/src/app/Backends/PGP.php b/src/app/Backends/PGP.php
--- a/src/app/Backends/PGP.php
+++ b/src/app/Backends/PGP.php
@@ -3,6 +3,7 @@
 namespace App\Backends;
 
 use App\User;
+use Illuminate\Support\Facades\DB;
 use Illuminate\Support\Facades\Storage;
 
 class PGP
@@ -81,6 +82,27 @@
         //        They are still in database and Roundcube hosts' filesystem
     }
 
+    /**
+     * Deleta a keypair from DNS and Enigma keyring.
+     *
+     * @param \App\User $user  User object
+     * @param string    $email Email address of the key
+     *
+     * @throws \Exception
+     */
+    public static function keyDelete(User $user, string $email): void
+    {
+        // Start with the DNS, it's more important
+        self::keyUnregister($email);
+
+        // Remove the whole Enigma keyring (if it's a delete user account)
+        if ($user->email === $email) {
+            self::homedirCleanup($user);
+        } else {
+            // TODO: remove only the alias key from Enigma keyring
+        }
+    }
+
     /**
      * List (public and private) keys from a user keyring.
      *
@@ -110,9 +132,24 @@
      * @param string $email Email address
      * @param string $key   The ASCII-armored key content
      */
-    public static function keyRegister(string $email, string $key)
+    private static function keyRegister(string $email, string $key): void
     {
-        // TODO
+        list($local, $domain) = \App\Utils::normalizeAddress($email, true);
+
+        DB::beginTransaction();
+
+        $domain = \App\PowerDNS\Domain::firstOrCreate([
+                'name' => '_woat.' . $domain,
+        ]);
+
+        \App\PowerDNS\Record::create([
+                'domain_id' => $domain->id,
+                'name' => sha1($local) . '.' . $domain->name,
+                'type' => 'TXT',
+                'content' => 'v=woat1,public_key=' . $key
+        ]);
+
+        DB::commit();
     }
 
     /**
@@ -120,9 +157,18 @@
      *
      * @param string $email Email address
      */
-    public static function keyUnregister(string $email)
+    private static function keyUnregister(string $email): void
     {
-        // TODO
+        list($local, $domain) = \App\Utils::normalizeAddress($email, true);
+
+        $domain = \App\PowerDNS\Domain::where('name', '_woat.' . $domain)->first();
+
+        if ($domain) {
+            $fqdn = sha1($local) . '.' . $domain->name;
+
+            // For now we support only one WOAT key record
+            $domain->records()->where('name', $fqdn)->delete();
+        }
     }
 
     /**
diff --git a/src/app/Jobs/PGP/KeyDeleteJob.php b/src/app/Jobs/PGP/KeyDeleteJob.php
new file mode 100644
--- /dev/null
+++ b/src/app/Jobs/PGP/KeyDeleteJob.php
@@ -0,0 +1,43 @@
+<?php
+
+namespace App\Jobs\PGP;
+
+use App\Jobs\UserJob;
+
+/**
+ * Delete a GPG keypair for a user (or alias) from the DNS and Enigma storage.
+ */
+class KeyDeleteJob extends UserJob
+{
+    /**
+     * Create a new job instance.
+     *
+     * @param int    $userId    User identifier.
+     * @param string $userEmail User email address of the key
+     *
+     * @return void
+     */
+    public function __construct(int $userId, string $userEmail)
+    {
+        $this->userId = $userId;
+        $this->userEmail = $userEmail;
+    }
+
+    /**
+     * Execute the job.
+     *
+     * @return void
+     *
+     * @throws \Exception
+     */
+    public function handle()
+    {
+        $user = $this->getUser();
+
+        if (!$user) {
+            return;
+        }
+
+        \App\Backends\PGP::keyDelete($user, $this->userEmail);
+    }
+}
diff --git a/src/app/Jobs/PGP/KeyUnregisterJob.php b/src/app/Jobs/PGP/KeyUnregisterJob.php
deleted file mode 100644
--- a/src/app/Jobs/PGP/KeyUnregisterJob.php
+++ /dev/null
@@ -1,42 +0,0 @@
-<?php
-
-namespace App\Jobs\PGP;
-
-use App\Jobs\CommonJob;
-
-/**
- * Remove the GPG key from the WOAT DNS system.
- */
-class KeyUnregisterJob extends CommonJob
-{
-    /**
-     * The email property.
-     *
-     * @var string
-     */
-    protected $email;
-
-    /**
-     * Create a new job instance.
-     *
-     * @param string $email User email address for the key
-     *
-     * @return void
-     */
-    public function __construct(string $email)
-    {
-        $this->email = $email;
-    }
-
-    /**
-     * Execute the job.
-     *
-     * @return void
-     *
-     * @throws \Exception
-     */
-    public function handle()
-    {
-        \App\Backends\PGP::keyUnregister($this->email);
-    }
-}
diff --git a/src/app/Observers/UserAliasObserver.php b/src/app/Observers/UserAliasObserver.php
--- a/src/app/Observers/UserAliasObserver.php
+++ b/src/app/Observers/UserAliasObserver.php
@@ -86,7 +86,7 @@
             \App\Jobs\User\UpdateJob::dispatch($alias->user_id);
 
             if (Tenant::getConfig($alias->user->tenant_id, 'pgp.enable')) {
-                \App\Jobs\PGP\KeyUnregisterJob::dispatch($alias->alias);
+                \App\Jobs\PGP\KeyDeleteJob::dispatch($alias->user_id, $alias->alias);
             }
         }
     }
diff --git a/src/app/Observers/UserObserver.php b/src/app/Observers/UserObserver.php
--- a/src/app/Observers/UserObserver.php
+++ b/src/app/Observers/UserObserver.php
@@ -188,6 +188,10 @@
         // FIXME: What do we do with user wallets?
 
         \App\Jobs\User\DeleteJob::dispatch($user->id);
+
+        if (\App\Tenant::getConfig($user->tenant_id, 'pgp.enable')) {
+            \App\Jobs\PGP\KeyDeleteJob::dispatch($user->id, $user->email);
+        }
     }
 
     /**
diff --git a/src/app/PowerDNS/Domain.php b/src/app/PowerDNS/Domain.php
--- a/src/app/PowerDNS/Domain.php
+++ b/src/app/PowerDNS/Domain.php
@@ -12,7 +12,10 @@
 
     protected $table = 'powerdns_domains';
 
-    public function bumpSerial()
+    /**
+     * Bump the SOA record serial
+     */
+    public function bumpSerial(): void
     {
         $soa = $this->records()->where('type', 'SOA')->first();
 
@@ -33,7 +36,12 @@
         $soa->save();
     }
 
-    public function getSerial()
+    /**
+     * Returns the SOA record serial
+     *
+     * @return string
+     */
+    public function getSerial(): string
     {
         $soa = $this->records()->where('type', 'SOA')->first();
 
@@ -42,10 +50,23 @@
         return $serial;
     }
 
+    /**
+     * Any DNS records assigned to this domain.
+     *
+     * @return \Illuminate\Database\Eloquent\Relations\HasMany
+     */
     public function records()
     {
-        return $this->hasMany('App\PowerDNS\Record', 'domain_id');
+        return $this->hasMany(Record::class, 'domain_id');
     }
 
-    //public function setSerial() { }
+    /**
+     * Any (additional) properties of this domain.
+     *
+     * @return \Illuminate\Database\Eloquent\Relations\HasMany
+     */
+    public function settings()
+    {
+        return $this->hasMany(DomainSetting::class, 'domain_id');
+    }
 }
diff --git a/src/app/Utils.php b/src/app/Utils.php
--- a/src/app/Utils.php
+++ b/src/app/Utils.php
@@ -311,29 +311,30 @@
      *
      * This means to lowercase and strip components separated with recipient delimiters.
      *
-     * @param string $address The address to normalize.
+     * @param ?string $address The address to normalize
+     * @param bool    $asArray Return an array with local and domain part
      *
-     * @return string
+     * @return string|array Normalized email address as string or array
      */
-    public static function normalizeAddress($address)
+    public static function normalizeAddress(?string $address, bool $asArray = false)
     {
-        $address = strtolower($address);
+        if ($address === null || $address === '') {
+            return $asArray ? ['', ''] : '';
+        }
+
+        $address = \strtolower($address);
 
         if (strpos($address, '@') === false) {
-            return $address;
+            return $asArray ? [$address, ''] : $address;
         }
 
         list($local, $domain) = explode('@', $address);
 
-        if (strpos($local, '+') === false) {
-            return "{$local}@{$domain}";
+        if (strpos($local, '+') !== false) {
+            $local = explode('+', $local)[0];
         }
 
-        $localComponents = explode('+', $local);
-
-        $local = array_shift($localComponents);
-
-        return "{$local}@{$domain}";
+        return $asArray ? [$local, $domain] : "{$local}@{$domain}";
     }
 
     /**
diff --git a/src/tests/Feature/Jobs/PGP/KeyCreateTest.php b/src/tests/Feature/Jobs/PGP/KeyCreateTest.php
--- a/src/tests/Feature/Jobs/PGP/KeyCreateTest.php
+++ b/src/tests/Feature/Jobs/PGP/KeyCreateTest.php
@@ -21,6 +21,7 @@
         $user = $this->getTestUser('john@kolab.org');
         UserAlias::where('alias', 'test-alias@kolab.org')->delete();
         PGP::homedirCleanup($user);
+        \App\PowerDNS\Domain::where('name', '_woat.kolab.org')->delete();
     }
 
     /**
@@ -31,6 +32,7 @@
         $user = $this->getTestUser('john@kolab.org');
         UserAlias::where('alias', 'test-alias@kolab.org')->delete();
         PGP::homedirCleanup($user);
+        \App\PowerDNS\Domain::where('name', '_woat.kolab.org')->delete();
 
         parent::tearDown();
     }
@@ -82,7 +84,21 @@
         $this->assertSame(true, $key->canEncrypt());
         $this->assertSame(false, $key->isRevoked());
 
-        // TODO: Assert the public key in DNS?
+        // Assert the public key in DNS
+        $dns_domain = \App\PowerDNS\Domain::where('name', '_woat.kolab.org')->first();
+        $this->assertNotNull($dns_domain);
+        $dns_record = $dns_domain->records()->where('type', 'TXT')->first();
+        $this->assertNotNull($dns_record);
+        $this->assertSame('TXT', $dns_record->type);
+        $this->assertSame(sha1('john') . '._woat.kolab.org', $dns_record->name);
+        $this->assertMatchesRegularExpression(
+            '/^v=woat1,public_key='
+                . '-----BEGIN PGP PUBLIC KEY BLOCK-----'
+                . '[a-zA-Z0-9\n\/+=]+'
+                . '-----END PGP PUBLIC KEY BLOCK-----'
+                . '$/',
+            $dns_record->content
+        );
 
         // Test an alias
         Queue::fake();
@@ -119,5 +135,7 @@
         $this->assertSame(false, $key->canSign());
         $this->assertSame(true, $key->canEncrypt());
         $this->assertSame(false, $key->isRevoked());
+
+        $this->assertSame(2, $dns_domain->records()->where('type', 'TXT')->count());
     }
 }
diff --git a/src/tests/Feature/Jobs/PGP/KeyDeleteTest.php b/src/tests/Feature/Jobs/PGP/KeyDeleteTest.php
new file mode 100644
--- /dev/null
+++ b/src/tests/Feature/Jobs/PGP/KeyDeleteTest.php
@@ -0,0 +1,71 @@
+<?php
+
+namespace Tests\Feature\Jobs\PGP;
+
+use App\Backends\PGP;
+use App\Backends\Roundcube;
+use App\User;
+use App\UserAlias;
+use Illuminate\Support\Facades\Queue;
+use Tests\TestCase;
+
+class KeyDeleteTest extends TestCase
+{
+    /**
+     * {@inheritDoc}
+     */
+    public function setUp(): void
+    {
+        parent::setUp();
+
+        $user = $this->getTestUser('john@kolab.org');
+        UserAlias::where('alias', 'test-alias@kolab.org')->delete();
+        PGP::homedirCleanup($user);
+        \App\PowerDNS\Domain::where('name', '_woat.kolab.org')->delete();
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public function tearDown(): void
+    {
+        $user = $this->getTestUser('john@kolab.org');
+        UserAlias::where('alias', 'test-alias@kolab.org')->delete();
+        PGP::homedirCleanup($user);
+        \App\PowerDNS\Domain::where('name', '_woat.kolab.org')->delete();
+
+        parent::tearDown();
+    }
+
+    /**
+     * Test job handle
+     *
+     * @group pgp
+     */
+    public function testHandle(): void
+    {
+        Queue::fake();
+
+        $user = $this->getTestUser('john@kolab.org');
+
+        // First run the key create job
+        $job = new \App\Jobs\PGP\KeyCreateJob($user->id, $user->email);
+        $job->handle();
+
+        // Assert the public key in DNS exist at this point
+        $dns_domain = \App\PowerDNS\Domain::where('name', '_woat.kolab.org')->first();
+        $this->assertNotNull($dns_domain);
+        $this->assertSame(1, $dns_domain->records()->where('type', 'TXT')->count());
+
+        // Run the job
+        $job = new \App\Jobs\PGP\KeyDeleteJob($user->id, $user->email);
+        $job->handle();
+
+        $this->assertSame(0, $dns_domain->records()->where('type', 'TXT')->count());
+
+        // Assert the created keypair parameters
+        $keys = PGP::listKeys($user);
+
+        $this->assertCount(0, $keys);
+    }
+}
diff --git a/src/tests/Feature/PowerDNS/DomainTest.php b/src/tests/Feature/PowerDNS/DomainTest.php
--- a/src/tests/Feature/PowerDNS/DomainTest.php
+++ b/src/tests/Feature/PowerDNS/DomainTest.php
@@ -18,11 +18,7 @@
     {
         parent::setUp();
 
-        $this->domain = Domain::firstOrCreate(
-            [
-                'name' => 'test-domain.com'
-            ]
-        );
+        $this->domain = Domain::firstOrCreate(['name' => 'test-domain.com']);
     }
 
     /**
@@ -35,36 +31,18 @@
         parent::tearDown();
     }
 
+    /**
+     * Test domain record creation (observer)
+     */
     public function testDomainCreate(): void
     {
         $this->assertCount(1, $this->domain->records()->where('type', 'SOA')->get());
         $this->assertCount(2, $this->domain->records()->where('type', 'NS')->get());
-    }
-
-    public function testCreateRecord(): void
-    {
-        $before = $this->domain->getSerial();
-
-        Record::create(
-            [
-                'domain_id' => $this->domain->id,
-                'name' => $this->domain->{'name'},
-                'type' => "MX",
-                'content' => '10 mx01.' . $this->domain->{'name'} . '.'
-            ]
-        );
-
-        Record::create(
-            [
-                'domain_id' => $this->domain->id,
-                'name' => 'mx01.' . $this->domain->{'name'},
-                'type' => "A",
-                'content' => '127.0.0.1'
-            ]
-        );
+        $this->assertCount(2, $this->domain->records()->where('type', 'A')->get());
+        $this->assertCount(5, $this->domain->records()->get());
 
-        $after = $this->domain->getSerial();
+        $this->assertCount(1, $this->domain->settings()->get());
 
-        $this->assertTrue($before < $after);
+        // TODO: Test content of every domain record/setting
     }
 }
diff --git a/src/tests/Feature/PowerDNS/RecordTest.php b/src/tests/Feature/PowerDNS/RecordTest.php
new file mode 100644
--- /dev/null
+++ b/src/tests/Feature/PowerDNS/RecordTest.php
@@ -0,0 +1,95 @@
+<?php
+
+namespace Tests\Feature\PowerDNS;
+
+use App\PowerDNS\Domain;
+use App\PowerDNS\Record;
+use Tests\TestCase;
+
+class RecordTest extends TestCase
+{
+    /** @var \App\PowerDNS\Domain $domain */
+    private $domain = null;
+
+    /**
+     * {@inheritDoc}
+     */
+    public function setUp(): void
+    {
+        parent::setUp();
+
+        $this->domain = Domain::firstOrCreate(['name' => 'test-domain.com']);
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public function tearDown(): void
+    {
+        $this->domain->delete();
+
+        parent::tearDown();
+    }
+
+    /**
+     * Test creating DNS records
+     */
+    public function testCreateRecord(): void
+    {
+        $before = $this->domain->getSerial();
+
+        Record::create([
+                'domain_id' => $this->domain->id,
+                'name' => $this->domain->{'name'},
+                'type' => "MX",
+                'content' => '10 mx01.' . $this->domain->{'name'} . '.'
+        ]);
+
+        $after = $this->domain->getSerial();
+
+        $this->assertTrue($before < $after);
+    }
+
+    /**
+     * Test updating DNS records
+     */
+    public function testUpdateRecord(): void
+    {
+        $record = Record::create([
+                'domain_id' => $this->domain->id,
+                'name' => $this->domain->{'name'},
+                'type' => "MX",
+                'content' => '10 mx01.' . $this->domain->{'name'} . '.'
+        ]);
+
+        $before = $this->domain->getSerial();
+
+        $record->content = 'test';
+        $record->save();
+
+        $after = $this->domain->getSerial();
+
+        $this->assertTrue($before < $after);
+    }
+
+    /**
+     * Test deleting DNS records
+     */
+    public function testDeleteRecord(): void
+    {
+        $record = Record::create([
+                'domain_id' => $this->domain->id,
+                'name' => $this->domain->{'name'},
+                'type' => "MX",
+                'content' => '10 mx01.' . $this->domain->{'name'} . '.'
+        ]);
+
+        $before = $this->domain->getSerial();
+
+        $record->delete();
+
+        $after = $this->domain->getSerial();
+
+        $this->assertTrue($before < $after);
+    }
+}
diff --git a/src/tests/Feature/UserTest.php b/src/tests/Feature/UserTest.php
--- a/src/tests/Feature/UserTest.php
+++ b/src/tests/Feature/UserTest.php
@@ -578,6 +578,40 @@
         $this->assertSame(0, $reseller_wallet->fresh()->balance);
     }
 
+    /**
+     * Test user deletion with PGP/WOAT enabled
+     */
+    public function testDeleteWithPGP(): void
+    {
+        Queue::fake();
+
+        // Test with PGP disabled
+        $user = $this->getTestUser('user-test@' . \config('app.domain'));
+
+        $user->tenant->setSetting('pgp.enable', 0);
+        $user->delete();
+
+        Queue::assertPushed(\App\Jobs\PGP\KeyDeleteJob::class, 0);
+
+        // Test with PGP enabled
+        $this->deleteTestUser('user-test@' . \config('app.domain'));
+        $user = $this->getTestUser('user-test@' . \config('app.domain'));
+
+        $user->tenant->setSetting('pgp.enable', 1);
+        $user->delete();
+        $user->tenant->setSetting('pgp.enable', 0);
+
+        Queue::assertPushed(\App\Jobs\PGP\KeyDeleteJob::class, 1);
+        Queue::assertPushed(
+            \App\Jobs\PGP\KeyDeleteJob::class,
+            function ($job) use ($user) {
+                $userId = TestCase::getObjectProperty($job, 'userId');
+                $userEmail = TestCase::getObjectProperty($job, 'userEmail');
+                return $userId == $user->id && $userEmail === $user->email;
+            }
+        );
+    }
+
     /**
      * Tests for User::aliasExists()
      */
@@ -822,7 +856,15 @@
         $user->tenant->setSetting('pgp.enable', 0);
 
         Queue::assertPushed(\App\Jobs\User\UpdateJob::class, 3);
-        Queue::assertPushed(\App\Jobs\PGP\KeyUnregisterJob::class, 1);
+        Queue::assertPushed(\App\Jobs\PGP\KeyDeleteJob::class, 1);
+        Queue::assertPushed(
+            \App\Jobs\PGP\KeyDeleteJob::class,
+            function ($job) use ($user) {
+                $userId = TestCase::getObjectProperty($job, 'userId');
+                $userEmail = TestCase::getObjectProperty($job, 'userEmail');
+                return $userId == $user->id && $userEmail === 'useralias2@useraccount.com';
+            }
+        );
 
         $aliases = $user->aliases()->get();
         $this->assertCount(1, $aliases);
diff --git a/src/tests/Unit/UtilsTest.php b/src/tests/Unit/UtilsTest.php
--- a/src/tests/Unit/UtilsTest.php
+++ b/src/tests/Unit/UtilsTest.php
@@ -7,6 +7,24 @@
 
 class UtilsTest extends TestCase
 {
+    /**
+     * Test for Utils::normalizeAddress()
+     */
+    public function testNormalizeAddress(): void
+    {
+        $this->assertSame('', \App\Utils::normalizeAddress(''));
+        $this->assertSame('', \App\Utils::normalizeAddress(null));
+        $this->assertSame('test', \App\Utils::normalizeAddress('TEST'));
+        $this->assertSame('test@domain.tld', \App\Utils::normalizeAddress('Test@Domain.TLD'));
+        $this->assertSame('test@domain.tld', \App\Utils::normalizeAddress('Test+Trash@Domain.TLD'));
+
+        $this->assertSame(['', ''], \App\Utils::normalizeAddress('', true));
+        $this->assertSame(['', ''], \App\Utils::normalizeAddress(null, true));
+        $this->assertSame(['test', ''], \App\Utils::normalizeAddress('TEST', true));
+        $this->assertSame(['test', 'domain.tld'], \App\Utils::normalizeAddress('Test@Domain.TLD', true));
+        $this->assertSame(['test', 'domain.tld'], \App\Utils::normalizeAddress('Test+Trash@Domain.TLD', true));
+    }
+
     /**
      * Test for Utils::powerSet()
      */