いそと申します。

他のDBでのSQLでは、Where句の順番がかなり重要だったりします。
オプティマイザさんの判断にもよると思うのですが、

SELECT count(*) as cnt
  FROM denpyou, denpyoumeisai
 WHERE denpyou.DenpyouNo = denpyuoumeisai.DenpyouNo
   AND T_Code = '123456' AND KikakuBangou = 'ABCD-1234';

ですと、先にDenpyouNoでの結合の後、T_CodeとKikakuBangouでの
絞込みを行っていますよね。。

先にT_CodeとKikakuBangouで絞り込んだ表イメージとJoinしたら、
どうなりますか？

いそ＠日本hp