Index: /trunk/src/VBox/Main/include/MediumImpl.h
===================================================================
--- /trunk/src/VBox/Main/include/MediumImpl.h	(revision 35981)
+++ /trunk/src/VBox/Main/include/MediumImpl.h	(revision 35982)
@@ -175,6 +175,9 @@
     Utf8Str getName();
 
-    bool addRegistry(const Guid& id);
-    bool removeRegistry(const Guid& id);
+    bool addRegistry(const Guid& id, bool fRecurse);
+private:
+    void addRegistryImpl(const Guid& id, bool fRecurse);
+public:
+    bool removeRegistry(const Guid& id, bool fRecurse);
     bool isInRegistry(const Guid& id);
     bool getFirstRegistryMachineId(Guid &uuid) const;
@@ -187,4 +190,5 @@
 
     const Guid* getFirstMachineBackrefId() const;
+    const Guid* getAnyMachineBackref() const;
     const Guid* getFirstMachineBackrefSnapshotId() const;
 
Index: /trunk/src/VBox/Main/src-server/MachineImpl.cpp
===================================================================
--- /trunk/src/VBox/Main/src-server/MachineImpl.cpp	(revision 35981)
+++ /trunk/src/VBox/Main/src-server/MachineImpl.cpp	(revision 35982)
@@ -7759,5 +7759,5 @@
             if (puuidRegistry)
                 // caller wants registry ID to be set on all attached media (OVF import case)
-                medium->addRegistry(*puuidRegistry);
+                medium->addRegistry(*puuidRegistry, false /* fRecurse */);
         }
 
@@ -8784,5 +8784,5 @@
     AutoWriteLock alock(pMedium COMMA_LOCKVAL_SRC_POS);
 
-    if (pMedium->addRegistry(uuid))
+    if (pMedium->addRegistry(uuid, false /* fRecurse */))
         // registry actually changed:
         mParent->addGuidToListUniquely(llRegistriesThatNeedSaving, uuid);
Index: /trunk/src/VBox/Main/src-server/MediumImpl.cpp
===================================================================
--- /trunk/src/VBox/Main/src-server/MediumImpl.cpp	(revision 35981)
+++ /trunk/src/VBox/Main/src-server/MediumImpl.cpp	(revision 35982)
@@ -3079,8 +3079,11 @@
  * Must have caller + locking!
  *
+ * If fRecurse == true, then additionally the media tree lock must be held for reading.
+ *
  * @param id
+ * @param fRecurse If true, recurses into child media to make sure the whole tree has registries in sync.
  * @return true if the registry was added; false if the given id was already on the list.
  */
-bool Medium::addRegistry(const Guid& id)
+bool Medium::addRegistry(const Guid& id, bool fRecurse)
 {
     // hard disks cannot be in more than one registry
@@ -3099,6 +3102,29 @@
     }
 
+    addRegistryImpl(id, fRecurse);
+
+    return true;
+}
+
+/**
+ * Private implementation for addRegistry() so we can recurse more efficiently.
+ * @param id
+ * @param fRecurse
+ */
+void Medium::addRegistryImpl(const Guid& id, bool fRecurse)
+{
     m->llRegistryIDs.push_back(id);
-    return true;
+
+    if (fRecurse)
+    {
+        for (MediaList::iterator it = m->llChildren.begin();
+             it != m->llChildren.end();
+             ++it)
+        {
+            Medium *pChild = *it;
+            // recurse!
+            pChild->addRegistryImpl(id, fRecurse);
+        }
+    }
 }
 
@@ -3109,8 +3135,11 @@
  * Must have caller + locking!
  *
+ * If fRecurse == true, then additionally the media tree lock must be held for reading.
+ *
  * @param id
+ * @param fRecurse If true, recurses into child media to make sure the whole tree has registries in sync.
  * @return
  */
-bool Medium::removeRegistry(const Guid& id)
+bool Medium::removeRegistry(const Guid& id, bool fRecurse)
 {
     for (GuidList::iterator it = m->llRegistryIDs.begin();
@@ -3121,4 +3150,16 @@
         {
             m->llRegistryIDs.erase(it);
+
+            if (fRecurse)
+            {
+                for (MediaList::iterator it = m->llChildren.begin();
+                     it != m->llChildren.end();
+                     ++it)
+                {
+                    Medium *pChild = *it;
+                    pChild->removeRegistry(id, true);
+                }
+            }
+
             return true;
         }
@@ -3359,4 +3400,31 @@
 
     return &m->backRefs.front().machineId;
+}
+
+/**
+ * Internal method which returns a machine that either this medium or one of its children
+ * is attached to. This is used for finding a replacement media registry when an existing
+ * media registry is about to be deleted in VirtualBox::unregisterMachine().
+ *
+ * Must have caller + locking, *and* caller must hold the media tree lock!
+ * @return
+ */
+const Guid* Medium::getAnyMachineBackref() const
+{
+    if (m->backRefs.size())
+        return &m->backRefs.front().machineId;
+
+    for (MediaList::iterator it = m->llChildren.begin();
+         it != m->llChildren.end();
+         ++it)
+    {
+        Medium *pChild = *it;
+        // recurse for this child
+        const Guid* puuid;
+        if ((puuid = pChild->getAnyMachineBackref()))
+            return puuid;
+    }
+
+    return NULL;
 }
 
Index: /trunk/src/VBox/Main/src-server/VirtualBoxImpl.cpp
===================================================================
--- /trunk/src/VBox/Main/src-server/VirtualBoxImpl.cpp	(revision 35981)
+++ /trunk/src/VBox/Main/src-server/VirtualBoxImpl.cpp	(revision 35982)
@@ -3716,5 +3716,6 @@
     GuidList llRegistriesThatNeedSaving;
     {
-        AutoWriteLock tlock(getMediaTreeLockHandle() COMMA_LOCKVAL_SRC_POS);
+        AutoReadLock tlock(getMediaTreeLockHandle() COMMA_LOCKVAL_SRC_POS);
+        // iterate over the list of *base* images
         for (MediaOList::iterator it = m->allHardDisks.getList().begin();
              it != m->allHardDisks.getList().end();
@@ -3726,12 +3727,15 @@
             AutoWriteLock mlock(pMedium COMMA_LOCKVAL_SRC_POS);
 
-            if (pMedium->removeRegistry(id))
+            if (pMedium->removeRegistry(id, true /* fRecurse */))
             {
-                // ID was found in medium's registry list:
-                // add a new one then
-                const Guid *puuidBetter = pMedium->getFirstMachineBackrefId();
+                // machine ID was found in base medium's registry list:
+                // move this base image and all its children to another registry then
+                // 1) first, find a better registry to add things to
+                const Guid *puuidBetter = pMedium->getAnyMachineBackref();
                 if (puuidBetter)
                 {
-                    pMedium->addRegistry(*puuidBetter);
+                    // 2) better registry found: then use that
+                    pMedium->addRegistry(*puuidBetter, true /* fRecurse */);
+                    // 3) and make sure the registry is saved below
                     addGuidToListUniquely(llRegistriesThatNeedSaving, *puuidBetter);
                 }