Sometimes free is better. Have you tried ffmpeg?
There's also an awful lot of software out there that uses ffmpeg under the hood. So, it's possible to put a friendlier face on this command-line tool.
While it doesn't support writing ON2 VP6, it does support earlier Flash formats. And as it comes with a wide variety of codecs (and more as optional plugins) it can at least be useful for moving out of your troublesome existing formats.
You could start by downloading an ffmpeg-based player (such as VLC, or the simple ffplay) and see if it will play your videos. If so, ffmpeg will almost certainly work with them. (Some of these players have additional codecs, though.)
I'd suggest looking-up ffmpeg and vlc on Wikipedia.
Oh, yes, VLC can itself encode, so that's an option too. Although it's a GUI program, it's not terribly user-friendly, though. Options, options, options...