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.

In reply to Re: Soliciting Multiline SIP Searching Suggestions by kyle
in thread Soliciting Multiline SIP Searching Suggestions by $dancarlson

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.