Ummm, the method doesn't break:

   f     f
  Z @   # @
  Z @   # @@@@@         
  Z @   #     @     
  Z @   # ZZZ @   
 f  @   # Z Zs@   
  # @   # ZZZ @    
  # @   #     @   
  # @   ##### @
  # @       # @
   s         e

Both of your examples merely illustrate te limitations previously mentioned: no guarantee of which exit a person will reach, and that you cannot start in the middle of a maze. (thanks Deejah for pointing out things when I'm tired)

In all cases of a static maze rendered in two dimensions (ie: only a wall or an exit, no sliding/changing bits, etc), your only options are a wall connected to other walls, a freestanding wall (which you'll never end up touching if you use the follow-the-wall-method from the outset), or an exit. It is possible that the only exit you will find will be the exit that you started from. You may not get the 'correct' exit, but otherwise you will reach an exit placed on the outside of the maze. Now if you remove your hand from a wall, you can get confused, and maybe touch a free-standing wall, but otherwise, keep on following.

However, you can treat any exit as a wall, thus if it is not the correct exit you want, and continue onwards to find all the other exterior exits.

  Z| |@
  Z| |@
  Z| |@
 d-e |@
2|   |@
 c-b |@
  #| |@
  #| |@
  #| |@
   a h

Enterance 1, from a-c to exit 2, conversely, you don't like exit 2, continue on as if 2 were a wall, and go a-f to exit 3. If you don't like exit 3, continue on as if 3 were a wall, and you wind up at 1 a-h (all the exits available to you)

Also, it must be noted that this solution only works if the exits (and enterance) are on the outermost wall of the maze. For mazes with exits located in the interior, use the Pledge algorithm, a form of wall-following which allows the jumps to islands, thus allowing it to solve mazes wall-following can't (thanks XWiz for the short description of pledge).

Now if I could just get e2 to quit reloading my old write-ups :P