diff --git a/openmp/libomptarget/src/omptarget.cpp b/openmp/libomptarget/src/omptarget.cpp
--- a/openmp/libomptarget/src/omptarget.cpp
+++ b/openmp/libomptarget/src/omptarget.cpp
@@ -564,9 +564,12 @@
 
       Device.ShadowMtx.lock();
       auto Entry = Device.ShadowPtrMap.find(Pointer_HstPtrBegin);
-      // If this pointer is not in the map we need to insert it.
-      if (Entry == Device.ShadowPtrMap.end()) {
-        // create shadow pointers for this entry
+      // If this pointer is not in the map we need to insert it. If the map
+      // contains a stale entry, we need to update it (e.g. if the pointee was
+      // deallocated and later on is reallocated at another device address).
+      if (Entry == Device.ShadowPtrMap.end() ||
+          Entry->second.TgtPtrVal != ExpectedTgtPtrBase) {
+        // create or update shadow pointers for this entry
         Device.ShadowPtrMap[Pointer_HstPtrBegin] = {
             HstPtrBase, PointerTgtPtrBegin, ExpectedTgtPtrBase};
         UpdateDevPtr = true;