Curious... how do you encode them? If its in H.264, try reducing the number of B-Frames in your encoding method. Just a guess, I've yet to try it myself.
No idea on the encoding... I'm not all that computer savvy
I just have these properties;
Windows Media Video V11
Audio: 192 Kbps, 48,000 Hz, 16 Bit, Stereo, WMA
Video: 29.970 fps, 1280x720 Progressive, WMV, 6.3 Mbps
Pixel Aspect Ratio: 1.000