Do you have another system you can use? Maybe with a video card on it that can help with pre-transcoding files?

This is what I ended up doing on mine. Was a big hit to my electric bill to pre-transcode the entire library (only for files that needed it), but now everything serves up in a flash. And the script runs as a nightly cron to catch any new stuff.

If you have to, maybe just dedicate the system you have here to transcode certain problematic content. Other than finding another download in a different format, I’m not sure there’s anything else you can practically do.