The problem must be with your input data, as I get a match with the following test cases :

sub check {
  $_ = "sendmail[[text to be captured from sendmail],relaying denied";

  (/sendmail\[.*?\[(.*?)\],.*?Relaying denied/i) and return ($1);
  (/gnu-pop3d\[.*?refused connect from (.*?)$/i) and return ($1);
  (/cucipop\[.*?authentication failure\s.*?\s(.*?)$/i) and return ($1)
+;
  
  return "No match found";
};
print check,"\n";
[download]

and also with

sub check {
  $_ = "sendmail[[text to be captured from sendmail],relaying denied";

  if (
    (/sendmail\[.*?\[(.*?)\],.*?Relaying denied/i) ||
    (/gnu-pop3d\[.*?refused connect from (.*?)$/i) ||
    (/cucipop\[.*?authentication failure\s.*?\s(.*?)$/i)
  ) { return ($1) };
  
  return "No match found";
};

print check,"\n";
[download]

The matches are exactly the same as your matches. My guess is, that you've got an extraneous \[ sprinkled in your sendmail RE.

perl -MHTTP::Daemon -MHTTP::Response -MLWP::Simple -e ' ;    # The  
$d = new HTTP::Daemon and fork and getprint $d->url and exit;#spider
($c = $d->accept())->get_request(); $c->send_response( new   #in the
HTTP::Response(200,$_,$_,qq(Just another Perl hacker\n))); ' #  web
[download]

You are right, but one thing is really strange - the same set of regex rules (currently 13 of them) works great on about 10 machines and doesn't work on those two (only).
The input line with sendmail contains

<sys_date> sendmail[pid]: <i>some stuf</i> relay=some.host.net [ip_add
+r], <i>some stuf</i> Relaying denied
[download]

Well - even if this rule or the input is wrong, then ok - it can be wrong - never mind - I'll fix it - but then, why it works on other computers?
I'm afraid of what I've mentioned - even very simple regex works only case-sensitive. For example this code I've written about a year ago:

#!/usr/bin/perl
use strict;

my @in;
open (FH, "ps ax |");
chomp(@in = <FH>);
close (FH);
$_ = join(//,@in);
chomp;
if (! /\/Rlogger.pl/i) { system("/etc/rc.d/rc.remote-logger") };
if (! /\/mle/i) { system("/etc/rc.d/rc.mle") };
[download]

I know it's dirty and not professional - sorry for that :-) Anyway mle is recognized as it should be but Rlogger.pl is not - it's done case-sensitive (on those 2 machines only).
I can always do some work-around to solve this problem in the other way, but I got supprised by those non-working regex lines. I can't find anything strange in system configuration, I've compiled perl from pure tarball several times on those machines and nothing helped so far :-(

Tnx for suggestions
Greetz, Tom.