This is a great question, thanks for providing the screencast which I'm sure took some effort to put together.
If I understand the problem correctly (and I'm only 60% sure I do--I haven't actually run your example yet), there are two parts to the solution. TL;DR: observer priorities, and freezeReactiveValue.
First, the observe(), observeEvent(), and outputs (via outputOptions()) can all take a priority field. If two observers/outputs have different priorities and both are invalidated, it's guaranteed that the one with the greater value for priority will be executed first (so priority=20 will happen before priority=10). The default priority is 0. So you should set the observers that reset brush, etc. to >0.
That won't solve the problem though; as you note, resetting row selection and brush only works "a little bit later". What is actually happening is that Shiny tries to stick to a "single source of truth", meaning, the true value of e.g. a brush exists only on the client; the value you read on the server, via input$brush, is just a reflection of what's on the client. So session$resetBrush doesn't directly change input$brush, but rather, sends a message to the client requesting that the brush is reset; and after the client has processed that message and actually reset the brush, it sends a message back to the server indicating the new value of the brush. This, as you note, can take an indeterminate amount of time.
Most of the time this approach works well enough, but in cases like yours this lag means there is a brief period (i.e. the rest of this reactive turn of the crank) where you have incorrect values in the `input` object. This usually manifests itself as a flicker (where the app briefly shows a nonsensical or erroneous set of outputs, then within a split second recalculating and giving the desired outputs), but in your case perhaps because data is actually being modified and saved during that period, your copy of the data frame actually gets corrupted (in the sense that the wrong rows have permanently be cleared or whatever).
You can fix this problem using the freezeReactiveValue function. At the time you call session$resetBrush (literally on the line above or the line below that call) you should call freezeReactiveValue(input, "brushId"). And the same for when you request a change to the row selection. What this basically does is put that particular input value in a frozen state, from that instant until the reactive graph reaches a temporary equilibrium (i.e. the rest of this turn of the crank, i.e. all outputs and observers have had their chance to execute). "Frozen state" means that any attempt to read the reactive value will fail in the same way that req(FALSE) would cause it to fail--silently.
So I'd try those two things--if they don't help, let us know.