What is your Sequence Preset? Does it match this footage perfectly?
You say that you tried several Export settings. That is not helpful. Which Export settings have you actually tried? There could be myriad poor choices, and with out knowing exactly, no one can suggest better.
Well, I need either a FLV with alpha channel or MOV with alpha channel.... To accomplish either are some specific settings.
However, with both I have maxed out the bitrates, the bitrate percentages, the "quality" to "best".... For the FLV I have tried 1 pass VBR, 2 pass VBR, CBR... pretty much everything listed here:
Post up a screen grab of the original footage with screen.
(or a link to the source of the footage)
BTW - I have had excellent success with FLV incl alpha
Alternatively - Have you tried creating your Key in AEFX and exporing with alpha?
I downloaded After Effects last night and it seemed to do a better job. I am still disappointed in the quality, but the project must go on.