EXISTSを使った相関サブクエリは、基本的に遅いです。
相関(サブクエリからメインを参照する)を利用しない方法を検討しましょう。
下記でどうでしょう。
SELECT
T1.社員No, T1.社員名, T1.所属
FROM
Mtbl_所属歴 T1
INNER JOIN
(SELECT
社員No, Min(開始日) AS Min開始日, Max(終了日) AS Max終了日
FROM Mtbl_所属歴
GROUP BY 社員No) Q1
ON T1.社員No=Q1.社員No
WHERE
T1.開始日>Min開始日 And T1.終了日<Max終了日;
これでもまだ遅いなら、
社員No、開始日、終了日 にインデックスを設定してください。
通報 ...