friedo,
I am assuming you want to use $mech_cgi->back() and $mech_mod->back() after testing each link. See this for an example where I did something similar.
Thanks, Limbic! That appears to be exactly what I needed. Mechanize is now happily following all the links. Who knew you had to press the back button to go back? :)
Isn't it amazing how the most baffling problems always seem to have the most obvious solutions?