The do stay in the exact position in the video.
If you have a score at 120 BPM in 4/4 time it takes 30 bars to play for 1 minute of real time. If you change the tempo to 100 BPM it only takes 25 bars to play for a minute, so a marker 1 minute from the start of the video will move from the start of bar 31 to the start of bar 26.
I don’t use Cubase so I don’t know what you did to “set the marker track to time code, so markers were locked and wouldn’t move,” but if you change the tempo a marker can’t be fixed to both the score and the picture.