Long story short, recent NVidia and ATI drivers bork DOS graphics modes. This fixes them. Reboot in safe mode, extract all files in the ZIP to a temp directory and run install.bat. Then restart, and you should have your full-screen DOS graphics back. If you ever update your graphics driver, you will have to do the patch again.
For Windows Vista, you have to use XP graphics drivers, because WDDM (Vista) drivers disable int 10h. This disables Aero, however.