I was having similar problems syncing Divx and Xvid files to my Gigabeat S60, which handles the same video formats as Windows Mobile and the Zune. Since Xvid and Divx are not MPEG-2, WMP doesn't use the DVD decoder on your machine.
I convert the files first in CuCuSoft Zune Video Converter and then sync the resulting WMV files. Since the CuCuSoft software converts it to a resolution and bit rate that my device supports natively, WMP doesn't need to transcode it and it just syncs it right away. TMPGEnc 4 Express is also a good piece software for doing video transcoding.
Yogi
Dell XPS 420: Core 2 Quad 2.4 GHz, 6 GB RAM, 2.34 TB total storage
Windows Vista Ultimate x64
2x ATI Digital Cable Tuners w/ CableCARD
1x HDHomeRun for 2x Clear QAM Tuners
3x Xbox 360 Extenders