Alright I had a chance to try Cave Story on a Vista computer.
I haven't found a good solution. The game is completely playable, but the text doesn't seem to clear itself. Now there is a Workaround that is annoying, but until a better solution is found this is what works I guess.
Here's my first solution:
Run Cave Story in full screen with at least one other thing open?, and alt tab each time it makes a mess.
For each time you switch, it forces a complete redraw of the screen or something. Resulting in the proper formatting. And a moment of legiable text, until something else overwrites itself.
A trick to speeding this up and not killing your monitor with resolution switching is matching your desktop resolution with cavestory... right click on desktop -> personalize -> Monitor -> advanced settings -> List All Modes -> and choose the resolution that you use in Cave Story [640x480 and probably the lower refresh rate]
I was trying to find a program to clear or refresh automatically without alt-tabbing but so far I haven't found one.