Ok,
I've had a look at a few of your clips, some observations:
The frame size for the clips is 480x360 (which is 4:3 aspect ratio) yet the active picture area is approx 480x316 (Which is neither 4:3 nor 16:9), and you obviously have letterboxing on the clip (black bars top and bottom).
The average data rate is around 2.3Mb/s
Suggestions:
The aspect ratio is wrong on the video, did you choose to add letterboxing or was it something in the workflow that added them?
You need to choose a total frame size which is either 4:3 or 16:9, you want to avoid letterboxing as these areas of black use up valuable bits of data. Do you shoot 4:3 or 16:9?
For 16:9 I'd suggest a frame size of 512x288, ideally or 480x270.
For 4:3 stick with 480x360.
You could probably get away with cutting your datarate down by at least 50%. If it still looks good to you at that datarate, then go down even further until it starts to look bad and work up slightly from there.
See how you go with that.
Re: Windows Media: It's an inferior video format to H.264 so you'll not get better quality. However if the majority of your viewers are very basic Windows PC users then you should probably offer it but it's pointless replacing the Quicktime with it.
Obviously every Mac user has Quicktime installed but any Windows user who has done even basic video viewing on-line should have Quicktime installed. Anybody who uses an iPod/iPhone or iTunes also has it. Obviously you can't view Windows Media on any type of iPod or iPhone.
In my 20 or so years of consulting in this area I've found that only ignorant users or arrogant Apple-haters prefer Windows Media over Quicktime.
You get so much of a better, fuller and more interactive experience with Quicktime. To prove my point compare the stuff
here with the stuff
here or
here
Like I said earlier, try scrubbing through a Windows movie or pausing it and then looking at it frame by frame.
Let us know how you get on.
__________________________________________________________________
Please post back saying what solved your problem. It could help others, and saying 'thanks' is free!