This issue has nothing to do with Vista. In fact, I think the exact same thing will happen in DOS Lemmings/ONML, if one of the vgagrX.dat, vgaspecX.dat, or levelX.dat files are missing or corrupted.
I think the game's assumption in the case of files it can't open, is that it thinks the user has been playing the game straight off of the floppy disc/CD-ROM, and the disc has been removed from the drive. Hence the message asking the user to insert disk.