I think you are being fooled by the lazy nature of LINQ here.
The sequence you create here:
var entitiesMarkedAsDelete = ChangeTracker.Entries<FooEntity>()
.Where(e => e.State==EntityState.Deleted);
.. is being evaluated each time it is being iterated, so the second time you foreach over it, you don't actually get any results back, since there are no entities in the deleted state anymore.
So to fix this, you simply have to pipe the sequence into fx. a list, by calling .ToList
on it:
var entitiesMarkedAsDelete = ChangeTracker.Entries<FooEntity>()
.Where(e => e.State==EntityState.Deleted).ToList();
That way both foreach statements will iterate over the same entities, and they should be deleted properly.