REMOVED is called even if the display object is not on the scene:
var childA : Sprite = new Sprite();
var childB : Sprite = new Sprite();
childA.addChild(childB);
childA.removeChild(childB);
childA was never in the scene display list, nor was childB.
Edit:
You can always use a weak link in your listener (the last parameter as true):
addEventListener(Event.REMOVED, onRemoved, false, 0, true);
source
share