I dunno exactly because this requires adjusted almost each and every frame of a sequence but I'm pretty sure Premier can do it easily. I am also certain Nero Vision Express can do it also but I am not a fan of that program grrrrrrrrrr.
hmm there is a program to do this and its in the back of my head, however i just have to say that to do this, ur looking at a full re-encode so that the words can actually just be pasted onto the video. Good question but i seriously have no idea why you would want to put watermarks on your vcds!