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
@@ -1969,20 +1969,21 @@
             );
 
             if ($row = $db->fetch_assoc()) {
-                // MariaDB's datetime output includes microseconds, we need to remove them,
-                // it must be "Y-m-d H:i:s" format
-                $synctime = preg_replace('/\.[0-9]+/', '', $row['synctime']);
+                // Don't use $row['synctime'] for the internal cache.
+                // The synctime of the found row is usually earlier than the requested synctime.
+                // Note: We use internal cache because there's a call to both hasChanges() and
+                // 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
-            $db->query(
-                "DELETE FROM `syncroton_relations_state`"
-                . " WHERE `device_id` = ? AND `folder_id` = ? AND `synctime` <> ?",
-                $device_key,
-                $folderid,
-                $synctime
-            );
+                // Cleanup: remove all records except the current one
+                $db->query(
+                    "DELETE FROM `syncroton_relations_state`"
+                    . " WHERE `device_id` = ? AND `folder_id` = ? AND `synctime` <> ?",
+                    $device_key,
+                    $folderid,
+                    $row['synctime'],
+                );
+            }
         }
 
         return $this->relations[$folderid][$synctime] ?? null;