It's not the game that's scaling. It attempts to set the monitor to the resolution of the game. Your graphics card configuration might be explicitly disallowing the resizing of the screen outside its own control panel or by some function calls. If the rest of the screen isn't black (i.e. you can see stuff that's not Cave Story), you are going to have to explore some other means of fixing it outside of what the game & DoConfig offer. If somehow you can't change some GPU config to fix it, you can use CSE2 Enhanced as a very last resort (unless you want to play with enhancements, that is). CSE2E resizes the window to fit the screen, but the renderer responsible for it may incorporate some ugly stretching/scaling/black bezels.
I have included a copy of CSE2E. It has been compiled for you. You should be able to run it with no problems out of the zip.