IMHO it is a design flaw if the deletion of a scene object is used to "steer" AI. If an object is dead or destroyed w.r.t. the game mechanics, then it is still existing in the scene. It may have to play a role (ruin, corpse, for looting, ...), some of them already mentioned in posts above. The target should be in the scene at least as long as any other game object is referring to it, simply because it is "in use" if being referred. Deletion is a low level mechanism; it could be run if higher levels are done with the object.
Running the AI every now and then has to be done anyway. What if the marines are attacked after they begun raiding the building? Do they react only after the building is destroyed? Hardly, I would say. So the regular checking for "is the currently followed plan still valid" will detect the destruction early enough. Hence there is also no real need to notify the marines as soon as the building collapses. It would look even artificial if 20 marines stop firing in the same millisecond.
AI need not be run on every frame for every unit and in full depth. Using a layered approach allows running the short tests more frequently, and computing higher layers only if the lower one has failed or finished. Also, ways exist to reduce the AI computations of a party by running full AI on a leader only, and letting it more or less directly control the other party members (this doesn't mean there must be an officer; the leadership can be as abstract as a concept of the party itself).