That applies only to certain conversions. If you convert highly compressed data to a less dense encoding you'll often lose nothing - and gain nothing except possibly compatibility, of course. There's also the term "transcode". Such a process usually doesn't cause any loss in quality it'll just put the data into different format so that your player of choice can handle it.

Even if the conversion is lossy, people usually exaggerate. The data you find on P2P is usually highly compressed any way and often poorly encoded. Sometimes it's above average and it gets better over the years but for home use or watching something on your crappy NTSC TV set, the little loss caused by converting is often - not always - negligible.
If you're that picky about quality - hey it's probably available in top-notch quality for a reasonable fair price.

Hint: The above contains a nice cute joke.

D-VHS? Tape? Ugh. Where can I purchase *anything* on D-VHS? That was dead before it was available. Tape has one use and none else: backups.

Laserdisc? Completely dead since DVD and the quality of DivX/XVid/MPEG-2/MPEG-4 can be much better than that. Often it's not really eventhough close. Well it depends on what you download. Crap stays crap at any resolution and color depth anyway.

VHS? Ugh, even MPEG-1 is as good as that and at least it'll still look the same in 5 years in contrast to the then-toasted VHS tape.

The problem of the original poster is likely just choice of the wrong tools. He should give mplayer, xine or VLC a try. Those - especially the first - play virtually any format there is - albeit I have to admit that may not be true on non-x86 platforms like a PPC Mac. However, those are free tools so it won't cost more than a small amount of time.