This didn't run as fast as the previously posted solution. It took me a while to wrap my head around the range operator, but I modified the code as follows, and now it runs faster than Kc12349's solution, though not quite as fast as ikegami's:

foreach ( split ( /^/m, $string ) )
{
  state $saw = 0;
  if ( my $seq = ( /^Heading Here:$/ .. /^Another Heading:$/ or
                   /^Another Heading:$/ .. /^End of section:/ ) )
  {
    redo if $seq =~ /E0$/;
    print $seq != 1 ? "  " : ! $saw++ ? "\n" : "";
  }
  print;
}
[download]

I do find this solution quite elegant though - thanks!