With such simple rules, you can get mazes like the one above, and harder still. I wanted to do something similar, and had one or two ideas I'd like to implement. For this, I have written a random "maze" creator. For now, it just populates a NxM matrix with integer values, representing walls, and outputs an ASCII or Postscript version of the "maze". I have quoted maze because it still does not qualify as a maze. Below you can see the output. There's still a lot of work to do for it to be useful, of course.
I had an internal debate on which language to implement this idea (and the following parts of this, which are the real maze generator and solution testers). I was thinking of either C or LISP, and settled for C. I am more fluent programming in C, moreover I had the doubt of what the speed constraints would be... when in doubt I go on and write it in C.
C code juicer: detecting copied programming assignments
Cron, diff & wget: Watch changes in a webpage
9 programming books I have read and somewhat liked...
8 reasons for re-inventing the wheel as a programmer
Approximating images with randomly placed translucent triangles