Well, pure 240p games are really problematic, as in order to get those games to scale properly in 480p, when I asked about Last Blade about 2 years ago I was told that if the pixels were stretched out a little bit Japanesecake said he could do it, but it would just be super time consuming. This is why those certain 2D games are just so problematic. I believe some upscalers use line doubling to fake a 480p signal to get around issues like this on modern HDTV's that don't support a 240p signal.
"The King of Fighters: Evolution, known as The King of Fighters '99 Evolution in Japan, is an updated version of The King of Fighters: Dream Match 1999 that was released for the Sega Dreamcast. First released in Japan on March 2000, the game did not see an American release until May 2001."
I would try that version of the game to see if it has VGA.