My favorite way to refactor loops that have the conditional in the middle is to use a subroutine because return in the middle of a subroutine seems an easy thing to understand (and to notice) when you come back to the code. It also avoids arguments with people who can't handle goto.

I also prefer to force eval to return a true value when it succeeds rather than checking $@ since there are cases where $@ can give the wrong impression about whether the eval was successful.

sub tieSession
{
    while(  1  ) {
        if(  eval {
                tie %session, 'Apache::Session::MySQL', $session, {
                    Handle => HH::DB->db_Main,
                    LockHandle => HH::DB->db_Main
                };
                1;
            }
        ) {
            return;
        }
        if(  $@ !~ /^Object does not exist/  ) {
            print $cgi->header;
            die_nice( 'Database Error',
                'Unable to connect at this time' );
        }
        undef $session;
    }
}
[download]

So I don't consider goto inherently evil. I prefer your original code over your coworkers in at least some respects. I really hate the use of Perl bare blocks as loops and think it often leads to more spagetti code than even goto does (expecting people to notice a "redo" burried so deep inside in order to realize that a loop was suddenly created out of a bare block).

But I wouldn't over golf for "excellence". Is the code working? There is probably something more important to be working on. (:

        - tye (but my friends call me "Tye")