diff --git a/docs/SQL/mysql.initial.sql b/docs/SQL/mysql.initial.sql
--- a/docs/SQL/mysql.initial.sql
+++ b/docs/SQL/mysql.initial.sql
@@ -60,6 +60,7 @@
     `lastsync` datetime DEFAULT NULL,
     `pendingdata` longblob,
     `client_id_map` longblob DEFAULT NULL,
+    `extra_data` longblob DEFAULT NULL,
     PRIMARY KEY (`id`),
     UNIQUE KEY `device_id--type--counter` (`device_id`,`type`,`counter`),
     CONSTRAINT `syncroton_synckey::device_id--syncroton_device::id` FOREIGN KEY (`device_id`) REFERENCES `syncroton_device` (`id`) ON DELETE CASCADE ON UPDATE CASCADE
@@ -96,16 +97,6 @@
     PRIMARY KEY (`id`)
 ) /*!40000 ENGINE=INNODB */ /*!40101 CHARACTER SET utf8 COLLATE utf8_general_ci */;
 
-CREATE TABLE IF NOT EXISTS `syncroton_modseq` (
-    `device_id` varchar(40) NOT NULL,
-    `folder_id` varchar(40) NOT NULL,
-    `synctime` datetime NOT NULL,
-    `data` longblob,
-    PRIMARY KEY (`device_id`,`folder_id`,`synctime`),
-    KEY `syncroton_modseq::device_id` (`device_id`),
-    CONSTRAINT `syncroton_modseq::device_id--syncroton_device::id` FOREIGN KEY (`device_id`) REFERENCES `syncroton_device` (`id`) ON DELETE CASCADE ON UPDATE CASCADE
-) /*!40000 ENGINE=INNODB */ /*!40101 CHARACTER SET utf8 COLLATE utf8_general_ci */;
-
 CREATE TABLE IF NOT EXISTS `syncroton_relations_state` (
     `device_id` varchar(40) NOT NULL,
     `folder_id` varchar(40) NOT NULL,
@@ -124,4 +115,4 @@
  PRIMARY KEY(`name`)
 ) /*!40000 ENGINE=INNODB */ /*!40101 CHARACTER SET utf8 COLLATE utf8_general_ci */;
 
-INSERT INTO `system` (`name`, `value`) VALUES ('syncroton-version', '2023100500');
+INSERT INTO `system` (`name`, `value`) VALUES ('syncroton-version', '2024031100');
diff --git a/docs/SQL/mysql/2024031100.sql b/docs/SQL/mysql/2024031100.sql
new file mode 100644
--- /dev/null
+++ b/docs/SQL/mysql/2024031100.sql
@@ -0,0 +1,3 @@
+
+ALTER TABLE `syncroton_synckey` ADD `extra_data` longblob DEFAULT NULL;
+DROP TABLE `syncroton_modseq`;
diff --git a/lib/ext/Syncroton/Command/Sync.php b/lib/ext/Syncroton/Command/Sync.php
--- a/lib/ext/Syncroton/Command/Sync.php
+++ b/lib/ext/Syncroton/Command/Sync.php
@@ -666,8 +666,7 @@
                             // fetch entries changed since last sync
                             $allChangedEntries = $dataController->getChangedEntries(
                                 $collectionData->collectionId,
-                                $collectionData->syncState->lastsync,
-                                $this->_syncTimeStamp,
+                                $collectionData->syncState,
                                 $collectionData->options['filterType']
                             );
 
@@ -996,6 +995,9 @@
                 if (!$emptySyncSupported || $collection->childNodes->length > 4 || $collectionData->syncState->counter != $collectionData->syncKey) {
                      $collections->appendChild($collection);
                 }
+
+                //Store next
+                $collectionData->syncState->extraData = $dataController->getExtraData($collectionData->folder);
             }
             
             if (isset($collectionData->syncState) && 
diff --git a/lib/ext/Syncroton/Data/AData.php b/lib/ext/Syncroton/Data/AData.php
--- a/lib/ext/Syncroton/Data/AData.php
+++ b/lib/ext/Syncroton/Data/AData.php
@@ -181,8 +181,10 @@
      * (non-PHPdoc)
      * @see Syncroton_Data_IData::getChangedEntries()
      */
-    public function getChangedEntries($_folderId, DateTime $_startTimeStamp, DateTime $_endTimeStamp = NULL, $filterType = NULL)
+    public function getChangedEntries($_folderId, Syncroton_Model_ISyncState $syncState, $filterType = NULL)
     {
+        $_startTimeStamp = $syncState->lastSync;
+        $_endTimeStamp = null;
         $folderId = $_folderId instanceof Syncroton_Model_IFolder ? $_folderId->id : $_folderId;
     
         $select = $this->_db->select()
@@ -272,7 +274,7 @@
         
         $addedEntries       = array_diff($allServerEntries, $allClientEntries);
         $deletedEntries     = array_diff($allClientEntries, $allServerEntries);
-        $changedEntries     = $this->getChangedEntries($folder->serverId, $syncState->lastsync, null, $folder->lastfiltertype);
+        $changedEntries     = $this->getChangedEntries($folder->serverId, $syncState, $folder->lastfiltertype);
         
         return count($addedEntries) + count($deletedEntries) + count($changedEntries);
     }
diff --git a/lib/ext/Syncroton/Data/IData.php b/lib/ext/Syncroton/Data/IData.php
--- a/lib/ext/Syncroton/Data/IData.php
+++ b/lib/ext/Syncroton/Data/IData.php
@@ -64,7 +64,14 @@
      */
     public function getAllFolders();
     
-    public function getChangedEntries($folderId, DateTime $startTimeStamp, DateTime $endTimeStamp = NULL, $filterType = NULL);
+    public function getChangedEntries($folderId, Syncroton_Model_ISyncState $syncState, $filterType = NULL);
+
+    /**
+     * Retrieve extra data that is stored with the sync key
+     * @return string|null
+     **/
+    public function getExtraData(Syncroton_Model_IFolder $folder);
+    
     
     /**
      * retrieve folders which were modified since last sync
diff --git a/lib/ext/Syncroton/Model/ISyncState.php b/lib/ext/Syncroton/Model/ISyncState.php
--- a/lib/ext/Syncroton/Model/ISyncState.php
+++ b/lib/ext/Syncroton/Model/ISyncState.php
@@ -20,6 +20,7 @@
  * @property    DateTime  lastsync
  * @property    string    pendingdata
  * @property    string    client_id_map
+ * @property    string    extraData
  */
 interface Syncroton_Model_ISyncState
 {
diff --git a/lib/kolab_sync_data.php b/lib/kolab_sync_data.php
--- a/lib/kolab_sync_data.php
+++ b/lib/kolab_sync_data.php
@@ -502,7 +502,7 @@
      *
      * @return array|int Search result as count or array of uids/objects
      */
-    protected function searchEntries($folderid, $filter = [], $result_type = self::RESULT_UID)
+    protected function searchEntries($folderid, $filter = [], $result_type = self::RESULT_UID, $extraData = null)
     {
         $result = $result_type == self::RESULT_COUNT ? 0 : [];
         $ts     = time();
@@ -510,7 +510,7 @@
         $found  = false;
 
         foreach ($this->extractFolders($folderid) as $fid) {
-            $search = $this->backend->searchEntries($fid, $this->device->deviceid, $this->modelName, $filter, $result_type, $force);
+            $search = $this->backend->searchEntries($fid, $this->device->deviceid, $this->modelName, $filter, $result_type, $force, $extraData);
             $found = true;
 
             switch ($result_type) {
@@ -555,44 +555,42 @@
      * get all entries changed between two dates
      *
      * @param string   $folderId
-     * @param DateTime $start
-     * @param DateTime $end
+     * @param Syncroton_Model_ISyncState $syncState
      * @param int      $filter_type
      *
      * @return array
      */
-    public function getChangedEntries($folderId, DateTime $start, DateTime $end = null, $filter_type = null)
+    public function getChangedEntries($folderId, Syncroton_Model_ISyncState $syncState, $filter_type = null)
     {
+        $start = $syncState->lastsync;
         $filter   = $this->filter($filter_type);
         $filter[] = ['changed', '>', $start];
 
-        if ($end) {
-            $filter[] = ['changed', '<=', $end];
-        }
-
-        return $this->searchEntries($folderId, $filter, self::RESULT_UID);
+        return $this->searchEntries($folderId, $filter, self::RESULT_UID, $syncState->extraData);
     }
 
     /**
      * Get count of entries changed between two dates
      *
      * @param string   $folderId
-     * @param DateTime $start
-     * @param DateTime $end
+     * @param Syncroton_Model_ISyncState $syncState
      * @param int      $filter_type
      *
      * @return int
      */
-    public function getChangedEntriesCount($folderId, DateTime $start, DateTime $end = null, $filter_type = null)
+    private function getChangedEntriesCount($folderId, Syncroton_Model_ISyncState $syncState, $filter_type = null)
     {
+        $start = $syncState->lastsync;
         $filter   = $this->filter($filter_type);
         $filter[] = ['changed', '>', $start];
 
-        if ($end) {
-            $filter[] = ['changed', '<=', $end];
-        }
+        return $this->searchEntries($folderId, $filter, self::RESULT_COUNT, $syncState->extraData);
+    }
 
-        return $this->searchEntries($folderId, $filter, self::RESULT_COUNT);
+ 
+    public function getExtraData(Syncroton_Model_IFolder $folder)
+    {
+        return $this->backend->getExtraData($folder->serverId, $this->device->deviceid);
     }
 
     /**
@@ -641,7 +639,7 @@
         // @phpstan-ignore-next-line
         $allClientEntries = $contentBackend->getFolderState($this->device, $folder, $syncState->counter);
         $allServerEntries = $this->getServerEntries($folder->serverId, $folder->lastfiltertype);
-        $changedEntries   = $this->getChangedEntriesCount($folder->serverId, $syncState->lastsync, null, $folder->lastfiltertype);
+        $changedEntries   = $this->getChangedEntriesCount($folder->serverId, $syncState, $folder->lastfiltertype);
         $addedEntries     = array_diff($allServerEntries, $allClientEntries);
         $deletedEntries   = array_diff($allClientEntries, $allServerEntries);
 
@@ -660,7 +658,7 @@
     public function hasChanges(Syncroton_Backend_IContent $contentBackend, Syncroton_Model_IFolder $folder, Syncroton_Model_ISyncState $syncState)
     {
         try {
-            if ($this->getChangedEntriesCount($folder->serverId, $syncState->lastsync, null, $folder->lastfiltertype)) {
+            if ($this->getChangedEntriesCount($folder->serverId, $syncState, $folder->lastfiltertype)) {
                 return true;
             }
 
diff --git a/lib/kolab_sync_data_contacts.php b/lib/kolab_sync_data_contacts.php
--- a/lib/kolab_sync_data_contacts.php
+++ b/lib/kolab_sync_data_contacts.php
@@ -470,14 +470,14 @@
      *
      * @return array|int Search result as count or array of uids/objects
      */
-    protected function searchEntries($folderid, $filter = [], $result_type = self::RESULT_UID)
+    protected function searchEntries($folderid, $filter = [], $result_type = self::RESULT_UID, $extraData = null)
     {
         // GAL Folder exists, return result from LDAP only
         if ($folderid === $this->galFolder && $this->hasGAL()) {
             return $this->searchGALEntries($filter, $result_type);
         }
 
-        $result = parent::searchEntries($folderid, $filter, $result_type);
+        $result = parent::searchEntries($folderid, $filter, $result_type, $extraData);
 
         // Merge results from LDAP
         if ($this->hasGAL() && !$this->isMultiFolder()) {
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
@@ -54,11 +54,11 @@
     protected $folder_meta;
     protected $folder_uids;
     protected $folders = [];
-    protected $modseq = [];
     protected $root_meta;
     protected $relations = [];
     protected $relationSupport = true;
     protected $tag_rts = [];
+    private $modseq = [];
 
     protected static $instance;
 
@@ -1139,10 +1139,11 @@
      * @param array  $filter      Filter
      * @param int    $result_type Type of the result (see kolab_sync_data::RESULT_* constants)
      * @param bool   $force       Force IMAP folder cache synchronization
+     * @param string $extraData   Extra data as extracted by the getExtraData during the last sync
      *
      * @return array|int Search result as count or array of uids
      */
-    public function searchEntries($folderid, $deviceid, $type, $filter, $result_type, $force)
+    public function searchEntries($folderid, $deviceid, $type, $filter, $result_type, $force, $extraData)
     {
         if ($type != self::MODEL_EMAIL) {
             return $this->searchKolabEntries($folderid, $deviceid, $type, $filter, $result_type, $force);
@@ -1150,15 +1151,12 @@
 
         $filter_str = 'ALL UNDELETED';
 
+        $getChangesMode = false;
         // convert filter into one IMAP search string
         foreach ($filter as $idx => $filter_item) {
             if (is_array($filter_item)) {
-                // This is a request for changes since last time
-                // we'll use HIGHESTMODSEQ value from the last Sync
                 if ($filter_item[0] == 'changed' && $filter_item[1] == '>') {
-                    $modseq_lasttime = $filter_item[2];
-                    $modseq_data     = [];
-                    $modseq = (array) $this->modseq_get($deviceid, $folderid, $modseq_lasttime);
+                    $getChangesMode = true;
                 }
             } else {
                 $filter_str .= ' ' . $filter_item;
@@ -1185,27 +1183,33 @@
             $this->storage->folder_sync($foldername);
         }
 
+        $modified = true;
         // We're in "get changes" mode
-        if (isset($modseq_data)) {
+        if ($getChangesMode) {
             $folder_data = $this->storage->folder_data($foldername);
-            $modified    = false;
 
-            // If previous HIGHESTMODSEQ doesn't exist we can't get changes
-            // We can only get folder's HIGHESTMODSEQ value and store it for the next try
-            // Skip search if HIGHESTMODSEQ didn't change
+            // If HIGHESTMODSEQ doesn't exist we can't get changes
             if (!empty($folder_data['HIGHESTMODSEQ'])) {
-                $modseq_data[$foldername] = $folder_data['HIGHESTMODSEQ'];
-                $modseq_old = $modseq[$foldername] ?? null;
-                if ($modseq_data[$foldername] != $modseq_old) {
-                    $modseq_update = true;
-                    if (!empty($modseq) && $modseq_old) {
-                        $modified    = true;
+                // Store modseq for later in getExtraData
+                if (!array_key_exists($deviceid, $this->modseq)) {
+                    $this->modseq[$deviceid] = [];
+                }
+                $this->modseq[$deviceid][$folderid] = $folder_data['HIGHESTMODSEQ'];
+                // After the initial sync we have no extraData
+                if ($extraData) {
+                    $modseq_old = json_decode($extraData)->modseq;
+                    // Skip search if HIGHESTMODSEQ didn't change
+                    if ($folder_data['HIGHESTMODSEQ'] == $modseq_old) {
+                        $modified = false;
+                    } else {
                         $filter_str .= " MODSEQ " . ($modseq_old + 1);
                     }
                 }
+            } else {
+                // We have no way of finding the changes.
+                // We could fall back to search by date or ignore changes, but both seems suboptimal.
+                throw new Syncroton_Exception_Status(Syncroton_Exception_Status::SERVER_ERROR);
             }
-        } else {
-            $modified = true;
         }
 
         // We could use messages cache by replacing search() with index()
@@ -1252,17 +1256,36 @@
             }
         }
 
-        if (!empty($modseq_update) && !empty($modseq_data)) {
-            $this->modseq_set($deviceid, $folderid, $this->syncTimeStamp, $modseq_data);
+        return $result;
+    }
+
+
+    /**
+     * Return extra data that is stored with the sync key and passed in during the search to find changes.
+     *
+     * @param string $folderid    Folder identifier
+     * @param string $deviceid    Device identifier
+     *
+     * @return string|null Extra data
+     */
+    public function getExtraData($folderid, $deviceid)
+    {
+        //We explicitly return a cached value that was used during the search.
+        //Otherwise we'd risk storing a higher modseq value and missing an update.
+        if (array_key_exists($deviceid, $this->modseq) && $value = $this->modseq[$deviceid][$folderid]) {
+            return json_encode(['modseq' => intval($value)]);
+        }
 
-            // if previous modseq information does not exist save current set as it,
-            // we would at least be able to detect changes since now
-            if (empty($result) && empty($modseq)) {
-                $this->modseq_set($deviceid, $folderid, $modseq_lasttime ?? 0, $modseq_data);
+        //If we didn't fetch modseq in the first place we have to fetch it now.
+        $foldername = $this->folder_id2name($folderid, $deviceid);
+        if ($foldername !== null) {
+            $folder_data = $this->storage->folder_data($foldername);
+            if (!empty($folder_data['HIGHESTMODSEQ'])) {
+                return json_encode(['modseq' => intval($folder_data['HIGHESTMODSEQ'])]);
             }
         }
 
-        return $result;
+        return null;
     }
 
     /**
@@ -1883,76 +1906,6 @@
         return $name;
     }
 
-    /**
-     * Save MODSEQ value for a folder
-     */
-    protected function modseq_set($deviceid, $folderid, $synctime, $data)
-    {
-        $synctime = $synctime->format('Y-m-d H:i:s');
-        $rcube    = rcube::get_instance();
-        $db       = $rcube->get_dbh();
-        $old_data = $this->modseq[$folderid][$synctime] ?? null;
-
-        if (empty($old_data)) {
-            $this->modseq[$folderid][$synctime] = $data;
-            $data = json_encode($data);
-
-            $db->set_option('ignore_key_errors', true);
-            $db->query(
-                "INSERT INTO `syncroton_modseq` (`device_id`, `folder_id`, `synctime`, `data`)"
-                . " VALUES (?, ?, ?, ?)",
-                $deviceid,
-                $folderid,
-                $synctime,
-                $data
-            );
-            $db->set_option('ignore_key_errors', false);
-        }
-    }
-
-    /**
-     * Get stored MODSEQ value for a folder
-     */
-    protected function modseq_get($deviceid, $folderid, $synctime)
-    {
-        $synctime = $synctime->format('Y-m-d H:i:s');
-
-        if (empty($this->modseq[$folderid][$synctime])) {
-            $this->modseq[$folderid] = [];
-
-            $rcube = rcube::get_instance();
-            $db    = $rcube->get_dbh();
-
-            $db->limitquery(
-                "SELECT `data`, `synctime` FROM `syncroton_modseq`"
-                . " WHERE `device_id` = ? AND `folder_id` = ? AND `synctime` <= ?"
-                . " ORDER BY `synctime` DESC",
-                0,
-                1,
-                $deviceid,
-                $folderid,
-                $synctime
-            );
-
-            if ($row = $db->fetch_assoc()) {
-                $synctime = $row['synctime'];
-                // @TODO: make sure synctime from sql is in "Y-m-d H:i:s" format
-                $this->modseq[$folderid][$synctime] = json_decode($row['data'], true);
-            }
-
-            // Cleanup: remove all records except the current one
-            $db->query(
-                "DELETE FROM `syncroton_modseq`"
-                . " WHERE `device_id` = ? AND `folder_id` = ? AND `synctime` <> ?",
-                $deviceid,
-                $folderid,
-                $synctime
-            );
-        }
-
-        return $this->modseq[$folderid][$synctime] ?? null;
-    }
-
     /**
      * Set state of relation objects at specified point in time
      */
diff --git a/lib/kolab_sync_storage_kolab4.php b/lib/kolab_sync_storage_kolab4.php
--- a/lib/kolab_sync_storage_kolab4.php
+++ b/lib/kolab_sync_storage_kolab4.php
@@ -560,4 +560,11 @@
         // TODO: Subscribe personal DAV folders, for now we assume all are subscribed
         // TODO: Subscribe shared DAV folders
     }
+
+    public function getExtraData($folderid, $deviceid) {
+        if (strpos($folderid, 'DAV:') === 0) {
+            return null;
+        }
+        return parent::getExtraData($folderid, $deviceid);
+    }
 }
diff --git a/tests/Sync/Sync/EmailTest.php b/tests/Sync/Sync/EmailTest.php
--- a/tests/Sync/Sync/EmailTest.php
+++ b/tests/Sync/Sync/EmailTest.php
@@ -158,13 +158,211 @@
     }
 
     /**
-     * Test updating message properties from client
+     * Test empty sync response
      *
      * @depends testSync
      */
-    public function testChangeFromClient($syncKey)
+    public function testEmptySync($syncKey)
+    {
+        $folderId = '38b950ebd62cd9a66929c89615d0fc04';
+        $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>
+                        <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;
+
+        $response = $this->request($request, 'Sync');
+
+        $this->assertEquals(200, $response->getStatusCode());
+        // We expect an empty response without a change
+        $this->assertEquals(0, $response->getBody()->getSize());
+
+        return $syncKey;
+    }
+
+    /**
+     * Test flag change
+     *
+     * @depends testEmptySync
+     */
+    public function testFlagChange($syncKey)
+    {
+        $this->assertTrue($this->markMailAsRead('INBOX', '*'));
+
+        $folderId = '38b950ebd62cd9a66929c89615d0fc04';
+        $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>
+                        <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;
+
+        $response = $this->request($request, 'Sync');
+
+        $this->assertEquals(200, $response->getStatusCode());
+        $dom = $this->fromWbxml($response->getBody());
+        $xpath = $this->xpath($dom);
+        // print($dom->saveXML());
+
+        $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(2, $xpath->query("{$root}/ns:Commands/ns:Change")->count());
+
+        return $syncKey;
+    }
+
+    /**
+     * Retry flag change
+     * Resending the same syncKey should result in the same changes.
+     *
+     * @depends testFlagChange
+     */
+    public function testRetryFlagChange($syncKey)
+    {
+        $syncKey--;
+        $folderId = '38b950ebd62cd9a66929c89615d0fc04';
+        $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>
+                        <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;
+
+        $response = $this->request($request, 'Sync');
+
+        $this->assertEquals(200, $response->getStatusCode());
+        $dom = $this->fromWbxml($response->getBody());
+        $xpath = $this->xpath($dom);
+        // print($dom->saveXML());
+
+        $root = "//ns:Sync/ns:Collections/ns:Collection";
+        $this->assertSame('1', $xpath->query("{$root}/ns:Status")->item(0)->nodeValue);
+        //FIXME I'm not sure why we get syncKey + 2, I suppose we just always increase the current synckey by one.
+        $this->assertSame(strval($syncKey += 2), $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(2, $xpath->query("{$root}/ns:Commands/ns:Change")->count());
+
+        $serverId1 = $xpath->query("{$root}/ns:Commands/ns:Change/ns:ServerId")->item(0)->nodeValue;
+
+        return [
+            'syncKey' => $syncKey,
+            'serverId' => $serverId1
+        ];
+    }
+
+    /**
+     * Test updating message properties from client
+     *
+     * @depends testRetryFlagChange
+     */
+    public function testChangeFromClient($values)
     {
-        $this->markTestIncomplete();
+        $folderId = '38b950ebd62cd9a66929c89615d0fc04';
+        $syncKey = $values['syncKey'];
+        $serverId = $values['serverId'];
+
+        $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:Syncroton="uri:Syncroton" xmlns:AirSyncBase="uri:AirSyncBase" xmlns:Email="uri:Email" xmlns:Email2="uri:Email2" xmlns:Tasks="uri:Tasks">
+                <Collections>
+                    <Collection xmlns:default="uri:Email" xmlns:default1="uri:AirSyncBase">
+                        <SyncKey>{$syncKey}</SyncKey>
+                        <CollectionId>{$folderId}</CollectionId>
+                        <Commands xmlns:default="uri:Email" xmlns:default1="uri:AirSyncBase">
+                            <Change xmlns:default="uri:Email" xmlns:default1="uri:AirSyncBase">
+                                <ServerId>{$serverId}</ServerId>
+                                <ApplicationData>
+                                    <Email:Read xmlns="uri:Email">0</Email:Read>
+                                    <Email:Flag xmlns="uri:Email"/>
+                                </ApplicationData>
+                            </Change>
+                        </Commands>
+                    </Collection>
+                </Collections>
+            </Sync>
+            EOF;
+
+        $response = $this->request($request, 'Sync');
+
+        $this->assertEquals(200, $response->getStatusCode());
+        $dom = $this->fromWbxml($response->getBody());
+        $xpath = $this->xpath($dom);
+        // print($dom->saveXML());
+
+        $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());
+        //The server doesn't have to report back successful changes
+        $this->assertSame(0, $xpath->query("{$root}/ns:Commands/ns:Change")->count());
+
+        $emails = $this->listEmails('INBOX', '*');
+        $uid = explode("::", $serverId)[1];
+        $this->assertSame(2, count($emails));
+        $this->assertTrue(!array_key_exists('SEEN', $emails[$uid]));
+
+        return [
+            'syncKey' => $syncKey,
+            'serverId' => $serverId
+        ];
     }
 
     /**
@@ -172,8 +370,99 @@
      *
      * @depends testChangeFromClient
      */
-    public function testDeleteFromClient($syncKey)
+    public function testDeleteFromClient($values)
     {
-        $this->markTestIncomplete();
+        $folderId = '38b950ebd62cd9a66929c89615d0fc04';
+        $syncKey = $values['syncKey'];
+        $serverId = $values['serverId'];
+
+        $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:Syncroton="uri:Syncroton" xmlns:AirSyncBase="uri:AirSyncBase" xmlns:Email="uri:Email" xmlns:Email2="uri:Email2" xmlns:Tasks="uri:Tasks">
+                <Collections>
+                    <Collection xmlns:default="uri:Email" xmlns:default1="uri:AirSyncBase">
+                        <SyncKey>{$syncKey}</SyncKey>
+                        <CollectionId>{$folderId}</CollectionId>
+                        <Commands xmlns:default="uri:Email" xmlns:default1="uri:AirSyncBase">
+                            <Delete xmlns:default="uri:Email" xmlns:default1="uri:AirSyncBase">
+                                <ServerId>{$serverId}</ServerId>
+                            </Delete>
+                        </Commands>
+                    </Collection>
+                </Collections>
+            </Sync>
+            EOF;
+
+        $response = $this->request($request, 'Sync');
+
+        $this->assertEquals(200, $response->getStatusCode());
+        $dom = $this->fromWbxml($response->getBody());
+        $xpath = $this->xpath($dom);
+        // print($dom->saveXML());
+
+        $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(0, $xpath->query("{$root}/ns:Commands/ns:Change")->count());
+        $this->assertSame(0, $xpath->query("{$root}/ns:Commands/ns:Delete")->count());
+
+        $emails = $this->listEmails('INBOX', '*');
+        $uid = explode("::", $serverId)[1];
+        $this->assertSame(2, count($emails));
+        $this->assertTrue($emails[$uid]['DELETED']);
+
+        return $syncKey;
     }
+
+
+    /**
+    * Test a sync key that doesn't exist yet.
+    * @depends testDeleteFromClient
+    */
+    public function testInvalidSyncKey($syncKey)
+    {
+        $syncKey++;
+        $folderId = '38b950ebd62cd9a66929c89615d0fc04';
+        $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>
+                        <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;
+
+        $response = $this->request($request, 'Sync');
+
+        $this->assertEquals(200, $response->getStatusCode());
+        $dom = $this->fromWbxml($response->getBody());
+        $xpath = $this->xpath($dom);
+        // print($dom->saveXML());
+
+        $root = "//ns:Sync/ns:Collections/ns:Collection";
+        $this->assertSame('3', $xpath->query("{$root}/ns:Status")->item(0)->nodeValue);
+        $this->assertSame('0', $xpath->query("{$root}/ns:SyncKey")->item(0)->nodeValue);
+
+        //We have to start over after this. The sync state was removed.
+        return 0;
+    }
+
 }
diff --git a/tests/SyncTestCase.php b/tests/SyncTestCase.php
--- a/tests/SyncTestCase.php
+++ b/tests/SyncTestCase.php
@@ -121,6 +121,24 @@
         return $uid;
     }
 
+    /**
+     * Mark an email message as read over IMAP
+     */
+    protected function markMailAsRead($folder, $uids)
+    {
+        $imap = $this->getImapStorage();
+        return $imap->set_flag($uids, 'SEEN', $folder);
+    }
+
+    /**
+     * List emails over IMAP
+     */
+    protected function listEmails($folder, $uids)
+    {
+        $imap = $this->getImapStorage();
+        return $imap->list_flags($folder, $uids);
+    }
+
     /**
      * Append an DAV object to a DAV/IMAP folder
      */
@@ -364,10 +382,10 @@
     /**
      * adapter for phpunit < 9
      */
-    protected function assertMatchesRegularExpression($arg1, $arg2)
+    public static function assertMatchesRegularExpression(string $arg1, string $arg2, string $message = ''): void
     {
         if (method_exists("PHPUnit\Framework\TestCase", "assertMatchesRegularExpression")) {
-            parent::assertMatchesRegularExpression($arg1, $arg2);
+            parent::assertMatchesRegularExpression($arg1, $arg2, $message);
         } else {
             parent::assertRegExp($arg1, $arg2);
         }