So at some point, when I had to navigate the SoS routinely, I had a bit of code/client script which did this for me, but have since lost it. It is based on a method that was posted to QHCF and is actually far superior to the 1-4 method above, and can be done by hand, though it takes a bit longer (hence the script). The basics are as follows:

Mark each room with distinct number of coins and keep a list of the exits taken from that room and what room they lead to and so on.

So on paper, you mark down something like this (Room # = number of coins in the room)

1) N S E W

Drop 1 coin, move north

1) N - 2, S E W
2) N S E W

Drop 1 coin, move north, now in room with 1 coin (Room #1)

1) N - 2, S E W
2) N - 1, S E W

Now you can either further explore the exits of room 2 (which never works with the 1-4 method) or you can move on to other exits from room 1, and you have it recorded. Lets say we further explore room 2, so we go north to room 2, and then go south... to no coins, so room 3.

1) N - 2, S E W
2) N - 1, S E W
3) N S E W

North takes us to a room with 2 coins, Room 2

1) N - 2, S E W
2) N - 1, S E W
3) N - 2, S E W

East takes us to a room with no coins,

1) N - 2, S E W
2) N - 1, S, E - 4, W
3) N - 2, S E W
4) N S E W

So on and so forth. So long as you have enough copper (and the right aliases/actions/triggers) this is trivially easy to script and will always yield ALL of a maze's exits, so long as you can either see them coming, or they aren't 1 way.