УДАЛЕНО вызывается, даже если объект отображения не находится на сцене:
var childA : Sprite = new Sprite();
var childB : Sprite = new Sprite();
childA.addChild(childB);
childA.removeChild(childB); // Event dispatched on childB
childA никогда не было в списке отображения сцены, равно как и childB.
Edit:
Вы всегда можете использовать слабую ссылку в вашем слушателе (последний параметр как true):
addEventListener(Event.REMOVED, onRemoved, false, 0, true);