Maybe their quality settings stink. Most likely they transcode with a low setting to keep size small. Maybe you should try converting yourself before uploading so they don't transcode. Try this or similar. Google "To FLV converter".