This idea looks like it is in the right direction.
If the address you seek is between a VAT line and a DESCRIPTION line, and that's the way that it always is, then, something like this might help?

This code looks for non-blank lines between and including lines starting with VAT and DESCRIPTION. So throw away those lines and any blank lines. The "trick" then comes down to figuring out when the address ends. If it is possible to write a simple regex that fits a UK postal code, then no state machine is required (when you see the postal code, the address record is done). Below I threw in an extra line feed when I see the postal code. Many variations are possible! Anyway, just an idea for you... Maybe this doesn't work if postal code is too variable and of course you'll have to refine my regex... But maybe this will spark another idea?

while (<DATA>)
{
    if (( /^VAT/.../^DESCRIPTION/) && (!/^s*$/))
    {          
       next if /^VAT/;
       next if /^DESCRIPTION/;
       print;              #these are the address lines
       print "\n" if (/\w+\d \d/); #the trick is to see
                           #when address is done, eg a postal code
    }
}
__END__
prints:

Miss Carol Hocker
177 Elm Road,
Brighton
East Sussex
BN2 7HB

Mr Whatever 
177 Elm Road,
Brighton
East Sussex
BN2 7HB

__DATA__
Invoice

Invoice No:    C0331-2008    
Invoice Date:27/02/2008
VAT No:     679 7113 03


Miss Carol Hocker
177 Elm Road,
Brighton
East Sussex
BN2 7HB




DESCRIPTION

blah..blah

Invoice No:    C0331-2008    
Invoice Date:27/02/2008
VAT No:     679 999 03


Mr Whatever 
177 Elm Road,
Brighton
East Sussex
BN2 7HB

DESCRIPTION

...something here....
[download]