If you’re having trouble using various free and commercial video converters where the convert file still under goes transcoding (re-converting) when syncing to your Zune, most likely your conversion settings fell out side of the required Zune specifications. For example, if your video resolution is 720×576 then the maximum frames per second you can use is 25 (as per the Zune specs). So if you used 30 fps then your video would under go transcoding during syncing.
I’ve tried to summarize these detailed specs on my Zune Video Specs page. My data might not be totally perfect, but it should be pretty close. Note, that following the instructions on my Video Conversion page should give you a high-quality video with no transcoding every time.