.. if I use the || instead of &&, the output I get contains contact_group output from PING ...

This doesn't seem possible to me: given the code you posted, no @input line with a 'PING' substring will be processed further. The && (logical and) of regex matches works for me as I expect:

c:\@Work\Perl\monks>perl -wMstrict -le
"my @input = (
   'PING foo wrong',
   'PING check_nrpe wrong',
   'PING contact_groups wrong',
   'PING check_nrpe contact_groups wrong',
   'PING contact_groups check_nrpe wrong',
   'foo wrong',
   'check_nrpe wrong',
   'contact_groups wrong',
   'check_nrpe contact_groups BINGO!',
   'contact_groups check_nrpe BINGO!',
   );
 ;;
 my $check = 'check_nrpe';
 my $con   = 'contact_groups';
 ;;
 for my $list (@input) {
   next if $list =~ /PING/;
   ;;
   print qq{'$list'} if $list =~ /$check/ && $list =~ /$con/;
   }
"
'check_nrpe contact_groups BINGO!'
'contact_groups check_nrpe BINGO!'
[download]

Update: Be aware that you are processing the example file on a line-by-line basis (update: with the code you've posted), not on a  define service { ... } block basis.