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]