You don't tell what 'recovery' means.
There are a lot of 'early VGA device' hits on google, and they all have to do with VGA cards detected incorrectly or interfering with on-board video. This is just one: http://www1.vobis.de/bbs/firmen/elsa_c99/graphics/erazor3/readme.txt
The best to do, in my opinion, is install a standard video driver when the new hardware wizard asks for it. Then go into Device Manager and disable this ghost device. A disabled device won't be detected as new hardware, but it won't do anything else either.
Hope this helps.
I had just performed a recovery on my Gateway 700 mhz cpu 256 mb memory, 15 gb hard drive. The operating system is Windows 98SE. The computer is running much better but now I get an error stating that new hardware has been found due to an early vga device, but cannot locate the software for it. I cancel it out after trying to locate the software and I have no conflicts in my device manager. I just keep getting the new hardware message each time I boot the computer.
I appreciate any ideas I can get,