diff --git a/src/backend/access/heap/tuptoaster.c b/src/backend/access/heap/tuptoaster.c
index 546f80f05c..01c392d546 100644
--- a/src/backend/access/heap/tuptoaster.c
+++ b/src/backend/access/heap/tuptoaster.c
@@ -1569,11 +1569,22 @@ toast_save_datum(Relation rel, Datum value,
 	 */
 	if (!OidIsValid(rel->rd_toastoid))
 	{
-		/* normal case: just choose an unused OID */
-		toast_pointer.va_valueid =
-			GetNewOidWithIndex(toastrel,
-							   RelationGetRelid(toastidxs[validIndex]),
-							   (AttrNumber) 1);
+		/*
+		 * Normal case: just choose an unused OID. But we must scan the TOAST
+		 * table using SnapshotToast to ensure that the value does not exists.
+		 * Note that GetNewOidWithIndex() scans the table with SnapshotDirty
+		 * and that may not see a RECENTLY_DEAD tuple. But such tuples are
+		 * visible to SnapshotToast and hence we must refrain from using such
+		 * OIDs. Otherwise toast_fetch_datum() or friends might see duplicate
+		 * OIDs, leading to all kinds of errors.
+		 */
+		do
+		{
+			toast_pointer.va_valueid =
+				GetNewOidWithIndex(toastrel,
+						RelationGetRelid(toastidxs[validIndex]),
+						(AttrNumber) 1);
+		} while (toastrel_valueid_exists(toastrel, toast_pointer.va_valueid));
 	}
 	else
 	{
diff --git a/src/backend/access/transam/xlog.c b/src/backend/access/transam/xlog.c
index b4fd8395b7..ba8b969cc2 100644
--- a/src/backend/access/transam/xlog.c
+++ b/src/backend/access/transam/xlog.c
@@ -9785,11 +9785,21 @@ xlog_redo(XLogReaderState *record)
 								  checkPoint.nextXid))
 			ShmemVariableCache->nextXid = checkPoint.nextXid;
 		LWLockRelease(XidGenLock);
-		/* ... but still treat OID counter as exact */
-		LWLockAcquire(OidGenLock, LW_EXCLUSIVE);
-		ShmemVariableCache->nextOid = checkPoint.nextOid;
-		ShmemVariableCache->oidCount = 0;
-		LWLockRelease(OidGenLock);
+
+		/*
+		 * In an ONLINE checkpoint, don't update the nextOid counter. If there
+		 * was no XLOG_NEXTOID record seen since the starting checkpoint, then
+		 * we continue to believe that the current value is correct. If we saw
+		 * a XLOG_NEXTOID record, then we should rather use that and not
+		 * overwrite with a potentially old value, thus issuing duplicate
+		 * OIDs when we are fully up.
+		 *
+		 * If you're still curious why that can happen, note that the online
+		 * checkpoint may have started before our original redo position and
+		 * hence it may have value later made stale by an explicit
+		 * XLOG_NEXTOID.
+		 */
+
 		MultiXactAdvanceNextMXact(checkPoint.nextMulti,
 								  checkPoint.nextMultiOffset);