I had this problem on my PC as well. It was very EVIL!
It happened when I changed my video card...
Unfortunately I am using Windows XP still, so the solution may vary.
If you have a NVIDIA card, maybe you can use the same solution that I used :
First what was helpful, was my monitor's menu button has an information sub category that shares what my current refresh rate actually is.
Check out what it is when running full-screen for Cave Story with tearing.
After figuring that out (I think mine was 640x480 75Hz originally)?
Right click desktop or goto start menu -> NVIDIA
Open up NVIDIA control panel and select :
Change Resolution
Then select Custom Resolution...
(WARNING IF YOU DONT KNOW WHAT YOU ARE DOING YOU COULD DAMAGE YOUR MONITOR ... or so they say)
Create one for 640x480 progressive 60 Hz (or maybe 50 if 60 ends up not working... I mean Cave Story is running at 50 fps...)
And check mark that resolution after a successful test.
[I further went and created another 640x480 progressive 75 Hz (or whatever your monitor is currently using that causes tearing], and uncheck that.
Now um... try restarting the PC, run cave story and see if windows uses the new 60 Hz 640x480. [Check with your monitor if possible]
Hopefully that did the trick... If not you need to do what I did next :
Download a free program called PowerStrip. Install that. "And aim for the big sucker!" [... whoops CS quote.. but who said that? Oh Chaco..]
After installing PowerStrip, create a Display Profile called Cave Story...
Move the window to your monitor you will play Cave Story on...
Choose 640x480 resolution.
For refresh rate, choose Custom timing. And maybe go into the Advanced timing options :
MAYBE then I went into Custom resolutions and chose predefined resolution 640x480p (HDTV derived) [press 6 until you see it]
Then close it I guess...
My options in the advanced timing options read something like :
Pixel clock 145.800 MHz, Scan rate 65.089 kHZ and Refresh rate 59.770 Hz
I think what I did was typed in 60 in Hz and it did that then I hit ok.
Also btw, it has Real-time adjustment. I have that checked; I think I had Cave Story open while I was adjusting it in windowed mode (but in the new 640x480 resolution) then just adjust that till it looks good... supposebly.
After hitting OK. Save your profile as Cave Story.
Next up :
I did application profile for Cave Story, or the mod I wanted to play...
Select the Cave Story display profile that you created a minute ago. And check Apply this profile whenever program starts.
That should have it set...
You can do additional options if you want like hide desktop or shut off other monitors while you are playing ... etc Up to you.
When it loads make sure it is running the new Hz you selected and not still using the old.
If the game loads funny and off-centered, alt tab it; then click on it again. It SHOULD be using the custom Hz. If it isn't try it again...
Anyways, ONCE you finally figure it out and get it working. It should miraculously fix itself so you don't have to run powerstrip anymore and fool with this. [by automatically choosing the new resolution] ... (probably after restarting or whatnot)
I don't THINK I'm missing any steps I did... I may have deleted the old resolution also somewhere, I'm not certain.
I'd offer you some tea but...
I mean I'd offer you easier to read advice but it was just guesswork at the time, and since it's working I don't really want to mess it up again.
I pray for your victory...