You know, sometimes two regexen are better than one:

/$this/ && !/$that/
[download]

may be the best solution, especially if $this and $that that are not necessarily in order. Otherwise a quick look into perldoc perlre would reveal you that probably what you want is (?!$that).

You said what you want, just state it in perl:

if( $res =~ /58=Invalid/ and not $res =~ /59=3/ ) {
  grobble_error( $res );
} else {
  print "58=Invalid and 59=3\n";
}
[download]

If I understand what you want then the followin regex code using a negative lookahead assertion is one way to do the trick:

use strict;
use warnings;

while (<DATA>) {
    print "Match $_" if /58=Invalid(?:(?!59=3).)*$/;
}

__DATA__
58=Invalid Contract;59=3;45=Test;23=Test12
58=Invalid Contract;45=Test
[download]

Prints:

Match 58=Invalid Contract;45=Test
[download]