Brute force Delaunay triangulation algorithm complexity
A Delaunay triangulation can be considered as the lower convex hull of the 2d point set lifted to the paraboloid. Thus, if you take your 2d point set and assign to every point $(x_i,y_i)$ a $z$-coordinate $z_i=x_i^2+y_1^2$, then the projection of the lower convex hull into the $xy$-plane gives you the Delaunay triangulation.

Using this perspective, what does it mean for an edge $(p_i,p_j)$ to be illegal? First of all, for every triangulation $T$ we can use the parabolic map to get a 3d (triangulated) surface that projects down to $T$. Of course, this surface is not necessarily convex, if it would be convex, $T$ would be the Delaunay triangulation. Simply speaking, the edge $(p_i,p_j)$ is an obstruction for the convexity of the surface, a concave edge. When flipping this edge we change the situation on the lifted surface only locally. So lets look at the 4 points $p_i,p_j,p_k,p_l$. In 3d they form a tetrahedron, that projects down to quadrilateral. Since the two triangles $p_ip_jp_k$ and $p_ip_jp_l$ define the the concave edge $(p_i,p_j)$, the triangles $p_kp_lp_i$ and $p_kp_lp_j$ define the a convex edge $(p_l,p_k)$. Therefore, flipping an illegal edge corresponds to replacing a concave edge by a convex edge in the lifting. Notice that this flips might turn other convex edges to concave edges.


Remark: The image is not geometrically correct and should only be considered as a sketch.

Let $T'$ be the triangulation after the flip. The lifted surface of $T'$ "contains" the surface of $T$. By this I mean that if you watch the two surfaces from the $xy$ plane you see only triangles from the surface of $T'$ (or triangles that are in both surfaces). You could also say that the surface of $T'$ encloses more volume. Also, the edge $(p_i,p_j)$ lies now "behind" the lifted surface induced by $T'$ when watching from the $xy$ plane. 

During the flip sequence we get a sequence of surfaces with strictly increasing volume. Thus, the edge $(p_i,p_j)$ lies "behind" all these surfaces. Hence, it can never reappear during the flipping process. Since there are only $n$ choose 2 possible edges, we have at most $O(n^2)$ flips.