Robert--
5x enlargement for a standard 35mm frame yields a print of ~5x7.5 inches. Most would agree that even relatively simple optics should be able produce a negative that will yield a "good" print at a 5x enlargement. Regardless of how big your negative is, it's still a 5x enlargement, and this is a reasonable value.
The question is, what does your lab mean by "digital negative". Some people use that term to refer to a negative image produced on inkjet transparency film and used for contact printing. Others may use that term to refer to scanning the image and then outputting it back to film, usually after Photoshop-type adjustments are made. My question is, why bother to do either? If you have access to a flatbed scanner of modern vintage (like an Epson 4990 or V500/V700/V750), why not just scan the film strip yourself and output a print to the lab of your choice. Enough dots for a 5x enlargement (about 1500 DPI) is well within the capability of these scanners.
It's unlikely that your lab's processing machine can automatically scan the 24x96 frame...they're probably scanning it as a secondary operation anyway, possibly on a flatbed.
Regardless, there's no reason to go through a second film generation to get to the print you're talking about. Costco stores in the US can output up to 18 inches long (12"x18") for something like $4 or $5, just a little smaller than what you're looking for. Some labs can do up to 12x36 (for anywhere between $10 and $20)
If your lab can go right from scan to print, then it's just a matter of whether you want to pay them to do the work, or do it yourself.
Hope this helps--
Greg