There would be two possibilities here:

(1) Forcing flush of the previous operations on batch, just before to traverse association to a deleted entity
(2) Even better, skip the check if the operation queue contains the remove operation of referenced entity

I've implemented the latter. In my opinion, forcing flush should be considered the last option.