diff --git a/lib/kolab_sync_storage.php b/lib/kolab_sync_storage.php
--- a/lib/kolab_sync_storage.php
+++ b/lib/kolab_sync_storage.php
@@ -56,7 +56,7 @@
     protected $folders = [];
     protected $root_meta;
     protected $relations = [];
-    protected $relationSupport = true;
+    public $relationSupport = true;
     protected $tag_rts = [];
     private $modseq = [];
 
@@ -1564,9 +1564,18 @@
                 ];
             }
 
-            $now = new DateTime('now', new DateTimeZone('UTC'));
+            // If the new and the old timestamp are the same our cache breaks.
+            // We must preserve the previous changes, because if this function is rerun we must detect the same changes again.
+            if ($this->syncTimeStamp->format('Y-m-d H:i:s') == $since->format('Y-m-d H:i:s')) {
+                // Preserve the previous timestamp (relations_state_get just checks the overflow bucket first)
+                // FIXME: The one caveat is that we will still update the database and thus overwrite the old entry.
+                // That means if we rerun the same request, the changes will not be detected
+                // => We should not be dealing with timestamps really.
+                $this->relations[$folderid][$since->format('Y-m-d H:i:s') . "-1"] = $this->relations[$folderid][$since->format('Y-m-d H:i:s')];
+                $this->relations[$folderid][$since->format('Y-m-d H:i:s')] = null;
+            }
 
-            $this->relations_state_set($device_key, $folderid, $now, $data);
+            $this->relations_state_set($device_key, $folderid, $this->syncTimeStamp, $data);
         }
 
         // in mail mode return only message URIs
@@ -1920,27 +1929,25 @@
     public function relations_state_set($device_key, $folderid, $synctime, $relations)
     {
         $synctime = $synctime->format('Y-m-d H:i:s');
-        $rcube    = rcube::get_instance();
-        $db       = $rcube->get_dbh();
-        $old_data = $this->relations[$folderid][$synctime] ?? null;
 
-        if (empty($old_data)) {
+        // Protect against inserting the same values twice (this code can be executed twice in the same request)
+        if (!isset($this->relations[$folderid][$synctime])) {
+            $rcube    = rcube::get_instance();
+            $db       = $rcube->get_dbh();
             $this->relations[$folderid][$synctime] = $relations;
             $data = rcube_charset::clean(json_encode($relations));
 
-            $result = $db->query(
-                "INSERT INTO `syncroton_relations_state`"
-                . " (`device_id`, `folder_id`, `synctime`, `data`)"
-                . " VALUES (?, ?, ?, ?)",
-                $device_key,
-                $folderid,
-                $synctime,
-                $data
+            $result = $db->insert_or_update(
+                'syncroton_relations_state',
+                ['device_id' => $device_key, 'folder_id' => $folderid, 'synctime' => $synctime],
+                ['data'],
+                [$data]
             );
 
             if ($err = $db->is_error($result)) {
                 throw new Exception("Failed to save relation: {$err}");
             }
+
         }
     }
 
@@ -1951,9 +1958,11 @@
     {
         $synctime = $synctime->format('Y-m-d H:i:s');
 
-        if (empty($this->relations[$folderid][$synctime])) {
-            $this->relations[$folderid] = [];
-
+        //If we had a collision before
+        if (isset($this->relations[$folderid][$synctime . "-1"])) {
+            return $this->relations[$folderid][$synctime. "-1"];
+        }
+        if (!isset($this->relations[$folderid][$synctime])) {
             $rcube = rcube::get_instance();
             $db    = $rcube->get_dbh();
 
@@ -1975,10 +1984,11 @@
                 // getChangedEntries() in Sync. It's needed until we add some caching on a higher level.
                 $this->relations[$folderid][$synctime] = json_decode($row['data'], true);
 
-                // Cleanup: remove all records except the current one
+                // Cleanup: remove all records older than the current one.
+                // We must use the row's synctime, otherwise we would delete the record we just loaded
                 $db->query(
                     "DELETE FROM `syncroton_relations_state`"
-                    . " WHERE `device_id` = ? AND `folder_id` = ? AND `synctime` <> ?",
+                    . " WHERE `device_id` = ? AND `folder_id` = ? AND `synctime` < ?",
                     $device_key,
                     $folderid,
                     $row['synctime']
diff --git a/tests/Sync/Sync/RelationsTest.php b/tests/Sync/Sync/RelationsTest.php
new file mode 100644
--- /dev/null
+++ b/tests/Sync/Sync/RelationsTest.php
@@ -0,0 +1,202 @@
+<?php
+
+namespace Tests\Sync\Sync;
+
+class RelationsTest extends \Tests\SyncTestCase
+{
+
+    protected function initialSyncRequest($folderId) {
+        $request = <<<EOF
+            <?xml version="1.0" encoding="utf-8"?>
+            <!DOCTYPE AirSync PUBLIC "-//AIRSYNC//DTD AirSync//EN" "http://www.microsoft.com/">
+            <Sync xmlns="uri:AirSync">
+                <Collections>
+                    <Collection>
+                        <SyncKey>0</SyncKey>
+                        <CollectionId>{$folderId}</CollectionId>
+                    </Collection>
+                </Collections>
+            </Sync>
+            EOF;
+        return $this->request($request, 'Sync');
+    }
+
+    protected function syncRequest($syncKey, $folderId, $windowSize = null) {
+        $request = <<<EOF
+            <?xml version="1.0" encoding="utf-8"?>
+            <!DOCTYPE AirSync PUBLIC "-//AIRSYNC//DTD AirSync//EN" "http://www.microsoft.com/">
+            <Sync xmlns="uri:AirSync" xmlns:AirSyncBase="uri:AirSyncBase">
+                <Collections>
+                    <Collection>
+                        <SyncKey>{$syncKey}</SyncKey>
+                        <CollectionId>{$folderId}</CollectionId>
+                        <DeletesAsMoves>1</DeletesAsMoves>
+                        <GetChanges>1</GetChanges>
+                        <WindowSize>{$windowSize}</WindowSize>
+                        <Options>
+                            <FilterType>0</FilterType>
+                            <Conflict>1</Conflict>
+                            <BodyPreference xmlns="uri:AirSyncBase">
+                                <Type>2</Type>
+                                <TruncationSize>51200</TruncationSize>
+                                <AllOrNone>0</AllOrNone>
+                            </BodyPreference>
+                        </Options>
+                    </Collection>
+                </Collections>
+            </Sync>
+            EOF;
+        return $this->request($request, 'Sync');
+    }
+
+    /**
+     * Test Sync command
+     */
+    public function testRelationsSync()
+    {
+        $sync = \kolab_sync::get_instance();
+        if (!$sync->storage()->relationSupport) {
+            $this->markTestSkipped('No relation support');
+        }
+
+        $this->emptyTestFolder('INBOX', 'mail');
+        $this->emptyTestFolder('Configuration', 'configuration');
+        $this->registerDevice();
+
+        // Test INBOX
+        $folderId = '38b950ebd62cd9a66929c89615d0fc04';
+        $syncKey = 0;
+        $response = $this->initialSyncRequest($folderId);
+        $this->assertEquals(200, $response->getStatusCode());
+
+        $dom = $this->fromWbxml($response->getBody());
+        $xpath = $this->xpath($dom);
+
+        $this->assertSame('1', $xpath->query("//ns:Sync/ns:Collections/ns:Collection/ns:Status")->item(0)->nodeValue);
+        $this->assertSame(strval(++$syncKey), $xpath->query("//ns:Sync/ns:Collections/ns:Collection/ns:SyncKey")->item(0)->nodeValue);
+        $this->assertSame('Email', $xpath->query("//ns:Sync/ns:Collections/ns:Collection/ns:Class")->item(0)->nodeValue);
+        $this->assertSame($folderId, $xpath->query("//ns:Sync/ns:Collections/ns:Collection/ns:CollectionId")->item(0)->nodeValue);
+
+        // First we append 
+        $uid1 = $this->appendMail('INBOX', 'mail.sync1');
+        $uid2 = $this->appendMail('INBOX', 'mail.sync2');
+        $this->appendMail('INBOX', 'mail.sync1', ['sync1' => 'sync3']);
+        $this->appendMail('INBOX', 'mail.sync1', ['sync1' => 'sync4']);
+
+        $sync = \kolab_sync::get_instance();
+
+        $device = $sync->storage()->device_get(self::$deviceId);
+
+        //Add a tag
+        $sync->storage()->updateItem($folderId, $device['ID'], \kolab_sync_storage::MODEL_EMAIL, $uid1, null, ['categories' => ['test1']]);
+        sleep(1);
+
+        $response = $this->syncRequest($syncKey, $folderId, 10);
+        $this->assertEquals(200, $response->getStatusCode());
+        $dom = $this->fromWbxml($response->getBody());
+        $xpath = $this->xpath($dom);
+        $root = "//ns:Sync/ns:Collections/ns:Collection";
+        $this->assertSame('1', $xpath->query("{$root}/ns:Status")->item(0)->nodeValue);
+        $this->assertSame(strval(++$syncKey), $xpath->query("{$root}/ns:SyncKey")->item(0)->nodeValue);
+        $this->assertSame($folderId, $xpath->query("{$root}/ns:CollectionId")->item(0)->nodeValue);
+        $this->assertSame(4, $xpath->query("{$root}/ns:Commands/ns:Add")->count());
+
+        $root .= "/ns:Commands/ns:Add";
+        $this->assertSame(1, $xpath->query("{$root}/ns:ApplicationData/Email:Categories")->count());
+        $this->assertSame("test1", $xpath->query("{$root}/ns:ApplicationData/Email:Categories")->item(0)->nodeValue);
+
+        //Add a second tag
+        $sync->storage()->updateItem($folderId, $device['ID'], \kolab_sync_storage::MODEL_EMAIL, $uid1, null, ['categories' => ['test1', 'test2']]);
+        sleep(1); // Necessary to make sure we pick up on the tag.
+
+        $response = $this->syncRequest($syncKey, $folderId, 10);
+        $this->assertEquals(200, $response->getStatusCode());
+        $dom = $this->fromWbxml($response->getBody());
+        $xpath = $this->xpath($dom);
+
+        $root = "//ns:Sync/ns:Collections/ns:Collection";
+        $this->assertSame('1', $xpath->query("{$root}/ns:Status")->item(0)->nodeValue);
+        $this->assertSame(strval(++$syncKey), $xpath->query("{$root}/ns:SyncKey")->item(0)->nodeValue);
+        $this->assertSame($folderId, $xpath->query("{$root}/ns:CollectionId")->item(0)->nodeValue);
+        $this->assertSame(0, $xpath->query("{$root}/ns:Commands/ns:Add")->count());
+        $this->assertSame(1, $xpath->query("{$root}/ns:Commands/ns:Change")->count());
+        $root .= "/ns:Commands/ns:Change";
+        $this->assertSame(1, $xpath->query("{$root}/ns:ApplicationData/Email:Categories")->count());
+        //FIXME not sure what I'm doing wrong, but the xml looks ok
+        $this->assertSame("test1test2", $xpath->query("{$root}/ns:ApplicationData/Email:Categories")->item(0)->nodeValue);
+
+        //Rerun the same command and make sure we get the same result
+        $syncKey--;
+        $root = "//ns:Sync/ns:Collections/ns:Collection";
+        $this->assertSame('1', $xpath->query("{$root}/ns:Status")->item(0)->nodeValue);
+        $this->assertSame(strval(++$syncKey), $xpath->query("{$root}/ns:SyncKey")->item(0)->nodeValue);
+        $this->assertSame($folderId, $xpath->query("{$root}/ns:CollectionId")->item(0)->nodeValue);
+        $this->assertSame(0, $xpath->query("{$root}/ns:Commands/ns:Add")->count());
+        $this->assertSame(1, $xpath->query("{$root}/ns:Commands/ns:Change")->count());
+        $root .= "/ns:Commands/ns:Change";
+        $this->assertSame(1, $xpath->query("{$root}/ns:ApplicationData/Email:Categories")->count());
+        //FIXME not sure what I'm doing wrong, but the xml looks ok
+        $this->assertSame("test1test2", $xpath->query("{$root}/ns:ApplicationData/Email:Categories")->item(0)->nodeValue);
+
+
+        // Assert the db state
+        $rcube = \rcube::get_instance();
+        $db    = $rcube->get_dbh();
+        $result = $db->query(
+            "SELECT `data`, `synctime` FROM `syncroton_relations_state`"
+            . " WHERE `device_id` = ? AND `folder_id` = ?"
+            . " ORDER BY `synctime` DESC",
+            $device['ID'],
+            $folderId
+        );
+        $data = [];
+        while ($state = $db->fetch_assoc($result)) {
+            $data[] = $state;
+        }
+        $this->assertSame(2, count($data));
+
+        // Reset to no tags
+        $sync->storage()->updateItem($folderId, $device['ID'], \kolab_sync_storage::MODEL_EMAIL, $uid1, null, ['categories' => []]);
+        sleep(1); // Necessary to make sure we pick up on the tag.
+
+        $response = $this->syncRequest($syncKey, $folderId, 10);
+        $this->assertEquals(200, $response->getStatusCode());
+        $dom = $this->fromWbxml($response->getBody());
+        $xpath = $this->xpath($dom);
+
+        $root = "//ns:Sync/ns:Collections/ns:Collection";
+        $this->assertSame('1', $xpath->query("{$root}/ns:Status")->item(0)->nodeValue);
+        $this->assertSame(strval(++$syncKey), $xpath->query("{$root}/ns:SyncKey")->item(0)->nodeValue);
+        $this->assertSame($folderId, $xpath->query("{$root}/ns:CollectionId")->item(0)->nodeValue);
+        $this->assertSame(0, $xpath->query("{$root}/ns:Commands/ns:Add")->count());
+        $this->assertSame(1, $xpath->query("{$root}/ns:Commands/ns:Change")->count());
+        $root .= "/ns:Commands/ns:Change";
+        $this->assertSame(0, $xpath->query("{$root}/ns:ApplicationData/Email:Categories")->count());
+        //FIXME this currently fails because we omit the empty categories element
+        // $this->assertSame("", $xpath->query("{$root}/ns:ApplicationData/Email:Categories")->item(0)->nodeValue);
+        
+
+        // Assert the db state
+        $result = $db->query(
+            "SELECT `data`, `synctime` FROM `syncroton_relations_state`"
+            . " WHERE `device_id` = ? AND `folder_id` = ?"
+            . " ORDER BY `synctime` DESC",
+            $device['ID'],
+            $folderId
+        );
+        $data = [];
+        while ($state = $db->fetch_assoc($result)) {
+            $data[] = $state;
+        }
+        $this->assertSame(2, count($data));
+
+        $response = $this->syncRequest($syncKey, $folderId, 10);
+        $this->assertEquals(200, $response->getStatusCode());
+        // We expect an empty response without a change
+        $this->assertEquals(0, $response->getBody()->getSize());
+        // print($dom->saveXML());
+
+        return $syncKey;
+    }
+}
+
diff --git a/tests/SyncTestCase.php b/tests/SyncTestCase.php
--- a/tests/SyncTestCase.php
+++ b/tests/SyncTestCase.php
@@ -51,6 +51,7 @@
         $db->query('DELETE FROM syncroton_data');
         $db->query('DELETE FROM syncroton_data_folder');
         $db->query('DELETE FROM syncroton_content');
+        $db->query('DELETE FROM syncroton_relations_state');
 
         self::$client = new \GuzzleHttp\Client([
                 'http_errors' => false,
@@ -87,6 +88,7 @@
             $db->query('DELETE FROM syncroton_device');
             $db->query('DELETE FROM syncroton_synckey');
             $db->query('DELETE FROM syncroton_folder');
+            $db->query('DELETE FROM syncroton_relations_state');
         }
     }
 
@@ -116,7 +118,7 @@
         $uid = $imap->save_message($folder, $source, '', $is_file);
 
         if ($uid === false) {
-            exit("Failed to append mail into {$folder}");
+            exit("Failed to append mail {$filename} into {$folder}");
         }
 
         return $uid;