there is no GOOD way to lose quality, all you can do is PREVENT a lot of quality loss. it's the same with mp3 compression and when an image is reduced (size, resolution). once the information is gone, you can't put it back in without the source.
when you re-encode, what you get is essentially a photocopy of a photocopy. to prevent the quality degradation, you would need to increase the re-encode settings to grab as much of the copied quality as you can. most of the time it increases the file size considerably. for that I would use virtaldub. small download, free, it gives you access to almost all the encoders that are on your computer. works with most files formats.
I would recommend keeping the dimensions to be as close to the original as possible, and use any encoder that has a 2 pass encode, it takes longer but you'll get less quality degradation. windows media is able to do that, divx has an n encode pass, which you can have it run as many times as you like, to get better encoding with smaller file size.
I took a divx 5 music video lasting 4 min and encoded to wmv in about 30 min with ok quality. but increasing the file size by 3 times. time to encode vary depending on your computer specs.
if there's no specific reason why you would need to encode the video, I would just let it be.