Timecode makes all the worries about finding the correct shots from the original negative go away. The fact that "everything" is on videotape is not the issue. The fact that the effects are only on videotape is. Re-editing the episodes from the original negatives utilizing the timecode to match the mastered NTSC version with it ain't no thing. Trust me.
TOS might end up being the more difficult project, simply due to the age of the negative. TNG, and especially DS9, will be in much better shape and won't require as much work before they're transfered to HD.