Connect your camera to your computer via Firewire and capture the video via Premiere. It will capture the full resolution of your tape, which I would guess is 640×480 unless you recorded to HD MiniDV. Unfortunately, scaling up the video to 1080 will look pretty bad no matter what. You have a limited amount of information to work with and computers can’t really fill in all the missing detail.
I’d go the shape layer route. Draw a line with the pen tool, add trim paths, and you’re done! Ok, maybe not quite; you can spice it up of course, but that’s the basic idea.
In the future, use Toggle Transparency Grid button (the little checkerboard looking thing) underneath your composition to see what your which parts of your composition are transparent if exported with an alpha channel.
For future reference, this is usually caused by having Bezier (or non-linear) keyframes. If you right-click on your keyframes, you can change the interpolation to Linear.
Most video games now can be played a 60fps, so you should record your screen at that frame rate, put it in a 24fps or 30fps timeline, and do some time-remapping to achieve the effect.