There are a number of possibilities:
the higher the temperature -> the higher the internal coil resistance -> the lower the current flowing through those coils -> the lower the torque.
Other possibilities that I can think of are
- the magnets temporarily losing magnetism (you say it works when it gets cool, so they aren't losing all their magnetism permanently),
- the motor binding up because of differential expansion, either inside the motor or in your mechanism.
- your mechanism itself is binding up, and the motor is fine
- the motor has some internal protection (I doubt this, but you never know).
Does it make sense? What are "okayish" temperatures for steper motors like NEMA17?
NEMA17 is a size. What a motor can actually stand depends on the motor itself. Particularly now that there is a strong hobby market, I wouldn't trust a particular size of motor (especially if you got it surplus) to behave like other same-sized motors.
I would expect a decent industrial motor to work over an industrial temperature range (i.e., 0C or even -20C to +55C) -- but that's kind of a "no true Scottsman" fallacy -- if it doesn't work over the temperature range I want, I'll just say "it's not decent then, is it?"
Ultimately, the motor works the way it works. If the manufacturer lives up to their promises, then you can look at the motor data and go with what it says. If there's no data, that's a big tell that you can't trust the motor. If you got the motor through surplus channels, or if the manufacturer isn't reputable, then all bets are off.