ある特定の動画だけかなりカタカタになる

MP4という形式は映像と音声の「入れ物」（コンテナフォーマット）でして、処理の重さや軽さ、画質や音質は中身の「コーデック」に影響されます。

同じクライアントさんから支給されたMP4でも、すべて同じ仕様とは限らないと思いますので、できましたら、「コーデック、フレームサイズ、フレームレート」といった情報で比較していただくと原因解明につながってゆくと思います（Premiere Proのプロジェクトパネルでプロパティを開いていただいたり、フリーソフトのMedia Infoなどをお使いいただくのも一つの方法です）。

仮に、問題が起きるファイルと問題が起きないファイルの仕様が全く同じですと、原因不明の現象ということになると思うのですが、そういった場合でもファイルの軽微な破損といった可能性を踏まえて、Adobe Media Encoderなどで再圧縮（とりあえず原因の切り分けでしたら、H.264「ソースの一致」あたりでよいと思います。）してからPremiere Proに読み込んでいただくといかがでしょうか。