Correct Clean-Up of Parent and Children with Callbacks (C++)

This design problem pops up again and again and I still don't have a nice solution for it. It might turn out to be a design pattern ;) Only, it seems to be very C++ specific (lack of garbage collection). Anyhow, here's the problem:

We have a parent object that keeps references to child objects. The parent's state depends on (some aggregate of) its children's states. In order to be notified of state changes in its children, it passes them a reference to itself. (In another variation it passes them a callback that the children can invoke to notify the parent. This callback is a closure that keeps a reference to the parent.) The application is heavily multi-threaded. Now, this setup is a whole hornet's nest of potential race conditions and dead locks. To understand why, here's a naive implementation:

class Parent {
 public:
   Parent() {
     children_["apple"].reset(new Child("apple", this));
     children_["peach"].reset(new Child("peach", this));
   }

   ~Parent() {
   }

   void ChildDone(const string& child) {
     cout << "Child is DONE: " << child << endl;
   }

  private:
   map<string, linked_ptr<Child> > children;
}; 

class Child {
  public:
   Child(const string& name, Parent* parent) 
       : name_(name), parent_(parent), done_(false) {}

   Foo(int guess) {
     if (guess == 42) done_ = true;
     parent->ChildDone(name_);
   }

  private:
   const string name_;
   Parent* parent_;
   bool done_; 
};

Potential issues:

I only scratched the surface, but one can think of other potential issues.

What I'm looking for is some advice on how to handle clean destruction of the parent in the face of threads, locks, and dynamic addition/removal of children. If anybody has come up with an elegant solution that is robust under multi-threaded deployment, please share. The keyword here is robust: it's easy to design a structure that comes with some huge caveats (child never calls parent, parent never calls child, no separate thread for callbacks, etc.), the challenge is to put as few restrictions on the programmer as possible.