Before you go to far, you may want to check out what the real problem with these videos is. For example, if they were encoded with a Flash knockoff, there may be encoding problems that would only be magnified if you tried to re-encode. For quality purposes, you should try to get back to the original .avi (or whatever). Test the video by playing it and if possible reading any meta data encoded in it. Here's the code for a simple vid player that will trace any meta data:
Code:
// Create a NetConnection object.
var netConn:NetConnection = new NetConnection();
// Create a local streaming connection.
netConn.connect(null);
// Create a NetStream object and define an onStatus() function.
var nStream:NetStream = new NetStream(netConn);
// Attach the NetStream video feed to the Video object.
my_video.attachVideo(nStream);
// Set the buffer time.
nStream.setBufferTime(20);
// Being playing the FLV file.
nStream.play("video1.flv");
// Trace the metadata.
nStream.onMetaData = function(myMeta) { 
     for (var i in myMeta) { 
          trace(i + ":\t" + myMeta[i]) 
     } 
};
In a new Flash doc, drag a new instance of a video onto the stage, give it an instance name of "my_video", and set some dimensions for it. Then add the AS.
Too large for the Web... what exactly do you mean? On short videos like the ones mentioned, it would typically not be the size of the file that is a problem for use on the Web, but rather the bitrate used to encode. Bitrates of 400kbps to 1000kbps or so, are deliverable over high speed Internet connections. If the video has no other problems except that the bitrate is too high.... 1500kbps or more, that could be a good thing if you try to re-encode because you can afford to lose some of the data when encoding at, say 500kbps.
To re-encode you could always embed the .flv directly into the timeline in a new Flash document, then "export" that as an avi, then encode back to .flv with Flash encoder. Just be sure not to compress the video when you export from Flash and be sure you set the appropriate video screen size and bitrate when you encode to .flv.
Best wishes,
Eye for Video
www.cidigitalmedia.com