複数のカラーを綺麗に抜きたい【Ultraキー】

Ckunさんの仰っている透明度マスクで分割する方法と、壁の部分は「塗りつぶし」で削除した方がうまくいくかもしれません。

ビデオトラックを３個にして、「塗りつぶし」を適用しています。
塗りつぶし１回で選択できない時は、２回以上でも適用できます。
壁の横線部分は、消えにくかったので「Color Replace」（バージョンによって日本語表記になっていると思います）で、周辺の色に変化させてから「塗りつぶし」を適用しました。
「塗りつぶし」の最終の設定は、下図のようにして下さい。

カメラが動いているか否かによって対応が変わってくるのですが、カメラが動いていない場合には、キーエフェクトを二重にかけるのではなく、グリーンバックがある部分と無い部分を別のレイヤー（トラック）で処理してマスクで切り分けてやると改善されると思います。

とはいえ、グリーンの端を厳密に切るのは難しいと思うので、1つ目のレイヤーは2重がけした現在の状態で、グリーンと壁の境界部分を細長くマスクで囲ったもの、2つ目のレイヤーはグリーンバック部分をマスクで囲って（灰色の壁を排除）グリーンのみに適したUltraキーを使用したもの、3つ目のレイヤーは壁部分のみをマスクで囲って壁の色を抜いたもの（灰色なので少々難しいかもしれないですが）、といった感じです。

グリーンからはみ出た部分の抜け具合は、あまり良くならないかもしれません。

カメラが動いていると、切り分けるマスクを追いかけなくてはならないので厄介です。小さな動きでしたらスタビライザーで止めてしまうのも一つの方法ですが、Huge21さんも触れられている通りAfter Effectsの方が痒いところに手が届きやすいと思います。

依頼されたものということですので、先方のご予算（と相応の労力）と求められるクオリティで方法を選んでゆくしかないのかなと、思います。

この素材の場合Premiere ProのUltraキーのみでクロマキー合成を行う事は非常に困難だと思われます。

対応できる処置としては、AfterEffectsのロトブラシやMochaAeなどを使用してロトスコープする事が有効な対応策です。（これは地道で高度な技術を求められる作業です…）