This is almost a copy of the example from the  "(?PARNO)" discussion in Extended Patterns in perlre. It needs Perl version 5.10+. Note there is an extraneous ) at the end of the  $s test string.

>perl -wMstrict -le
"use 5.010;
 ;;
 my $s =
   q{xx AND(random text) xx OR(more (and more)) AND (or (more (too))))
+};
 ;;
 my $intro = qr{ AND | OR }xms;
 my $nested_parens = qr{
   (
     \(
       ( (?: [^()]*+ | (?-2))* )
     \)
   )
   }xms;
 ;;
 while ($s =~ m{ ($intro) \s* $nested_parens }xmsg) {
   print qq{\$1 '$1'  \$2 '$2'  \$3 '$3'};
   }
"
$1 'AND'  $2 '(random text)'  $3 'random text'
$1 'OR'  $2 '(more (and more))'  $3 'more (and more)'
$1 'AND'  $2 '(or (more (too)))'  $3 'or (more (too))'
[download]

Update: Changed
    printf qq{\$1 '$1'  \$2 '$2'  \$3 '$3' \n}, $1, $2, $3;
in while-loop to something that makes more sense.