I had a compaq machine which was new sometime between 96 and 98 which had the “maintenance partition.” It wasn’t the BIOS that was on the hard drive, it was the BIOS configuration utility (which is still insanely stupid). In other words, you could boot and use the machine without this partition, but if you wanted to change the settings (e.g. when you add a hard drive) you were out of luck. Personally, I stay away from any machine that requires vendor-specific software (other than drivers, obviously) to use. There’s no good reason for it, and PC hardware companies aren’t exactly known for writing good software. Usually it’s a misguided excuse for you to see their logo as often as possible.
I have a Compaq Presario that I bought in August 2000, and it works perfectly fine, always has. I’ve also upgraded the RAM, among other things, with no problems. I got it from Best Buy for $450 after rebates and all that. Maybe I got lucky.