Well, I guess I sort of solved it. Every now and then, GetTicks would lag or spike on those old computers for some reason. And the way I was doing things, I suppose this crippled the game.
So now I use SDL_Delay to wait what's left of a frames time (as I saw was being done in examples), and when one of these wait times is too high(GetTicks messing up the calculating of how much is left to wait) I instead set it to an average of previous good values.
I still experience some skips in framerate, but at least it is playable on those computers now.
Edit: As for why it works fine, without skips, in debug... Is debug maybe running the process in some sort of higher priority perhaps?