Decremental reachability in a grid graph
By improving on @emab's idea, you can achieve $\Theta(\alpha(n^2))$ amortized time per deletion and query, where $\alpha$ is the inverse Ackermann function, i.e. almost constant.


Initialize a union-find data structure with an enry for each square of the grid graph and two entries each for the two pairs of outside faces top+right and bottom+left.
For an example of $n=3$, the faces $1,2,3,\ldots,9,A,B$ in the diagram below are initialized. Where $A,B$ are the outside faces split by the dashed lines.

When removing an edge call union() on the two squares (or the sqare and $A$ or $B$) separated by that edge.
To check connectivity, call find() on the faces $A$ and $B$. If the results differ, return true, else return false.