well, you always have the space vs speed trade-off. You could embed the flv conversion tool in a server side cgi/php script and host only the originals. That way you can direct link the originals for download and have the script do the preprocessing at request time for streaming.
I'm not sure how fast the conversion tools are though, that could be too slow and it'd be a huge wast not caching the conversion (at least temporarily if you don't want to permanently store them).