I got your expression to work on your test data with a couple of small changes, but if you have a huge file full of that stuff, you probably want something a little different. In particular, you want to keep .* from matching more than one record at once. Here's what I came up with:

use strict;
use warnings;

$_ = <<'END_SIP_LOG';
From: "Bungalo Bill" <sip:5555555555@11.11.11.111:22>;tag=SD223sd2-312
+33dss^M
To: <sip:6666666666@11.11.11.111:22>^M
Call-ID: SD0e1af02-4d8d3eesdfsdfsd44w5f6fdb77814d-h6030fd^M
END_SIP_LOG
    ;
s/\^M/\r/g;

my $NAME = 'Bungalo Bill';
my $INBOUND_NUMBER = '6666666666';

#my ($callid) = /From.*$NAME.*$INBOUND_NUMBER.*Call-ID:\s(.*)/s;

my ($callid) = m{ From:    \s "\Q$NAME\E"                  .*? \r \n?
                  To:      \s <sip: \Q$INBOUND_NUMBER\E \@ .*? \r \n?
                  Call-ID: \s (\S+)                        .*? \r \n?
             }xms;

print "callid = '$callid'\n";
__END__
callid = 'SD0e1af02-4d8d3eesdfsdfsd44w5f6fdb77814d-h6030fd'
[download]

I'm not sure if you have straight \r as line endings or the more likely \r\n, so the pattern matches either one.

Updated to format the pattern prettier.