diff --git a/src/requester/instance-id.c b/src/requester/instance-id.c
index 3d39fd8..b746a96 100644
--- a/src/requester/instance-id.c
+++ b/src/requester/instance-id.c
@@ -7,11 +7,20 @@
 #include <stdlib.h>
 #include <unistd.h>
 
+#define BIT(i) (1UL << (i))
+
 #define PLDM_TID_MAX 256
 #define PLDM_INST_ID_MAX 32
 
+/* We need to track our allocations explicitly due to OFD lock merging/splitting
+ */
+struct pldm_tid_state {
+	pldm_instance_id_t prev;
+	uint32_t allocations;
+};
+
 struct pldm_instance_db {
-	pldm_instance_id_t prev[PLDM_TID_MAX];
+	struct pldm_tid_state state[PLDM_TID_MAX];
 	int lock_db_fd;
 };
 
@@ -39,7 +48,7 @@
 
 	/* Initialise previous ID values so the next one is zero */
 	for (int i = 0; i < PLDM_TID_MAX; i++) {
-		l_ctx->prev[i] = 31;
+		l_ctx->state[i].prev = 31;
 	}
 
 	/* Lock database may be read-only, either by permissions or mountpoint
@@ -89,16 +98,21 @@
 		return -EINVAL;
 	}
 
-	l_iid = ctx->prev[tid];
+	l_iid = ctx->state[tid].prev;
 	if (l_iid >= PLDM_INST_ID_MAX) {
 		return -EPROTO;
 	}
 
-	while ((l_iid = iid_next(l_iid)) != ctx->prev[tid]) {
+	while ((l_iid = iid_next(l_iid)) != ctx->state[tid].prev) {
 		struct flock flop;
 		off_t loff;
 		int rc;
 
+		/* Have we already allocated this instance ID? */
+		if (ctx->state[tid].allocations & BIT(l_iid)) {
+			continue;
+		}
+
 		/* Derive the instance ID offset in the lock database */
 		loff = tid * PLDM_INST_ID_MAX + l_iid;
 
@@ -138,7 +152,8 @@
 		/* F_UNLCK is the type of the lock if we could successfully
 		 * promote it to F_WRLCK */
 		if (flop.l_type == F_UNLCK) {
-			ctx->prev[tid] = l_iid;
+			ctx->state[tid].prev = l_iid;
+			ctx->state[tid].allocations |= BIT(l_iid);
 			*iid = l_iid;
 			return 0;
 		}
@@ -163,6 +178,11 @@
 	struct flock flop;
 	int rc;
 
+	/* Trying to free an instance ID that is not currently allocated */
+	if (!(ctx->state[tid].allocations & BIT(iid))) {
+		return -EINVAL;
+	}
+
 	flop = cflu;
 	flop.l_start = tid * PLDM_INST_ID_MAX + iid;
 	rc = fcntl(ctx->lock_db_fd, F_OFD_SETLK, &flop);
@@ -173,5 +193,8 @@
 		return -EPROTO;
 	}
 
+	/* Mark the instance ID as no-longer allocated */
+	ctx->state[tid].allocations &= ~BIT(iid);
+
 	return 0;
 }
diff --git a/tests/instance-id.cpp b/tests/instance-id.cpp
index e26563f..99366b1 100644
--- a/tests/instance-id.cpp
+++ b/tests/instance-id.cpp
@@ -194,3 +194,40 @@
               0);
     ASSERT_EQ(pldm_instance_db_destroy(connections[0].db), 0);
 }
+
+TEST_F(PldmInstanceDbTest, allocAllInstanceIds)
+{
+    static constexpr pldm_tid_t tid = 1;
+
+    struct pldm_instance_db* db = nullptr;
+    std::array<pldm_instance_id_t, pldmMaxInstanceIds> iids = {};
+    pldm_instance_id_t extra;
+
+    ASSERT_EQ(pldm_instance_db_init(&db, dbPath.c_str()), 0);
+
+    for (auto& iid : iids)
+    {
+        EXPECT_EQ(pldm_instance_id_alloc(db, tid, &iid), 0);
+    }
+
+    EXPECT_EQ(pldm_instance_id_alloc(db, tid, &extra), -EAGAIN);
+
+    for (auto& iid : iids)
+    {
+        EXPECT_EQ(pldm_instance_id_free(db, tid, iid), 0);
+    }
+
+    EXPECT_EQ(pldm_instance_id_alloc(db, tid, &extra), 0);
+
+    ASSERT_EQ(pldm_instance_db_destroy(db), 0);
+}
+
+TEST_F(PldmInstanceDbTest, freeUnallocatedInstanceId)
+{
+    struct pldm_instance_db* db = nullptr;
+    const pldm_tid_t tid = 1;
+
+    ASSERT_EQ(pldm_instance_db_init(&db, dbPath.c_str()), 0);
+    EXPECT_NE(pldm_instance_id_free(db, tid, 0), 0);
+    ASSERT_EQ(pldm_instance_db_destroy(db), 0);
+}