diff --git a/swh/storage/tests/test_api_client.py b/swh/storage/tests/test_api_client.py
--- a/swh/storage/tests/test_api_client.py
+++ b/swh/storage/tests/test_api_client.py
@@ -82,4 +82,6 @@
 @pytest.mark.db
 @pytest.mark.property_based
 class PropTestRemoteStorage(CommonPropTestStorage, RemoteStorageFixture):
-    pass
+    @pytest.mark.skip('too slow')
+    def test_add_arbitrary(self):
+        pass
diff --git a/swh/storage/tests/test_storage.py b/swh/storage/tests/test_storage.py
--- a/swh/storage/tests/test_storage.py
+++ b/swh/storage/tests/test_storage.py
@@ -17,7 +17,7 @@
 
 from swh.model import from_disk, identifiers
 from swh.model.hashutil import hash_to_bytes
-from swh.model.hypothesis_strategies import origins
+from swh.model.hypothesis_strategies import origins, objects
 from swh.storage.tests.storage_testing import StorageTestFixture
 from swh.storage import HashCollision
 
@@ -3078,6 +3078,23 @@
         self.assertEqual(
             self.storage.origin_count('.*user1.*', regexp=False), 0)
 
+    @given(strategies.lists(objects(), max_size=2))
+    def test_add_arbitrary(self, objects):
+        self.reset_storage_tables()
+        for (obj_type, obj) in objects:
+            obj = obj.to_dict()
+            if obj_type == 'origin_visit':
+                origin_id = self.storage.origin_add_one(obj.pop('origin'))
+                if 'visit' in obj:
+                    del obj['visit']
+                self.storage.origin_visit_add(origin_id, **obj)
+            else:
+                method = getattr(self.storage, obj_type + '_add')
+                try:
+                    method([obj])
+                except HashCollision:
+                    pass
+
 
 @pytest.mark.db
 class TestLocalStorage(CommonTestStorage, StorageTestDbFixture,