Explanation:
the problem is that with ReadWrite Access strategy the insertion of a new cache entry get deferred to afterTransactionCompletion.
(see NaturalIdReadWriteAccess.java methods insert and afterInsert).
Thus the order of insert/delete get inverted:

1. ActionQueue processes inserts → insertion of a new cache entry get deferred to afterTransactionCompletion.
2. ActionQueue processes deletes→ removal of according cache entry (does not exist yet)
3. afterTransactionCompletion process → insertion of a cache entry with obsolete value

Later when creating a new instance with same NaturalId then the cache get not updated bacause of the existing entry.
As we see in the code below from NaturalIdReadWriteAccess.java the entry will only be created if not existing already.

@Override
	public boolean afterInsert(SharedSessionContractImplementor session, Object key, Object value) {
		try {
			writeLock().lock();
			Lockable item = (Lockable) getStorageAccess().getFromCache( key, session );
			if ( item == null) {
				getStorageAccess().putIntoCache(
						key,
						new Item( value, null, getRegion().getRegionFactory().nextTimestamp() ),
						session
				);