It's buried in the help file, but you prefix your string with (?s) - the regex implementation in LV is pretty dirty. The correct format for a regular expression is [delimiter][expression[delimiter][options], e.g: /(foo(?:.(?!foo))+)/sgi, which is my solution for your problem (but LV doesn't like lookaround). I'm spoiled by all the time I spent working with proper PCRE.
Well, you're parsing with regex - it's not the same thing as writing a parser. A true parser is written with the specific grammar of your subject in mind; not necessarily foo, followed by some stuff, and maybe another foo like the regex is doing. The "some stuff" part is something that regex is particularly bad for - unlimited quantifiers paired with dot or equivalent tend to be a sign that regex is the wrong tool. Regex is awesome when your subject is precise, but as you can see in your case, the variable-length payload is difficult to deal with elegantly. I bring this up especially because you mentioned that your header itself is variable, which is only going to further complicate things. You might be be successful with a regex, but it will be brittle and potentially very tedious to build.
Technically, yes, you can write a true parser using regex (and that's probably okay) but there's a very clear line (to me) when you're trying to do too much with one regular expression.
Darin's suggestion works correctly in LabVIEW (I don't think that it should), so you might be able to get away with finding an expression which works for the header and substituting it for your foo's.