How are you doing your install, interactively or by a batch file?
If by batch file, you'll need to run it interactively once to install MSDE. Then you can do future installs on that box by batch.
We ran into this when we upgraded from Tools Release 8.93 to 8.96.1.0 a month ago. You didn't used to have MSDE installed, but that's now enforced with 8.96.1.0 (and probably later, too).