The grid colorings approach is very cool! I don't think I've seen that one before, I bet you can somehow take that idea even further. You could also get similar effects by creating a regular uncolored (axis-aligned) grid maze and then rotate and re-rasterize it into another grid. But the grid coloring approach looks like it handles the boundary automatically.

One of these years I'll write it up, but I've played a lot with no-grid mazes, and once you get away from the 2d array, it opens up a lot of interesting possibilities. Prim's algorithm works equally well on a mesh where vertices have an arbitrary number of edges...