Unless I'm missing something, this can be done in O(n) time by tracking the connected components of wall (diagonally touching walls are connected). Placing a new wall creates an enclosed region if and only if it touches 2 separated sections of wall that are part of the same component.
The union-find disjoint sets algorithm can find whether they're in the same component. If a wall is added, it should be unioned with all adjacent walls. If a wall piece is removed, the components it was part of need to be recalculated, but it looks like that shouldn't happen more than once per frame.
In this case, the lookups of the union find algorithm will never take more than O(n) overhead per frame while checking all of up to n possible wall positions.