Search *patterns* match from a point then implicitly forward, even if the search is backward. So ?^\(foo\n\)\+ matches on line 5, the pattern doesn't cross lines backwards.
You can chain searches together with ; though. To search backwards for a line beginning with foo, then backwards for a line not beginning with foo, then forward one line:
?^foo?;?^\(foo\)\@!?+
That doesn't work if the foos start on line 1, the + offset won't wrap around the file end or beginning, (this appears to me to be undocumented). If that's a problem,
?^foo?;?^\(foo\)\@!?;/^foo
will work ('ws' being on). Unfortunately, back references don't reach across the ;, so if your "foo" was long, you might want to use a variable:
:let p = "foo"
:exe '?^' . p . '?;?^\(' . p . '\)\@!?;/^' . p
HTH, John Little