藤田です。

> 　このselectの前にexplainを付けて実行してみると、インデックスが使われて
> なかったりしません？
実行した結果です。
+---------------+--------+---------------------------+--------------+-------
--+--------------------------+-------+-------------+
| table              | type   | possible_keys             | key          |
key_len | ref                      | rows  | Extra       |
+---------------+--------+---------------------------+--------------+-------
--+--------------------------+-------+-------------+
| denpyoumeisai | ref    | kikakubangou,primarykey   | kikakubangou |
256 | const                    | 70849 | Using where |
| denpyou       | eq_ref | PRIMARY,primarykey,T_Code | PRIMARY      |
25 | denpyoumeisai.DenpyouNo |     1 | Using where |
+---------------+--------+---------------------------+--------------+-------
--+--------------------------+-------+-------------+
2 rows in set (0.00 sec)


> ちなみに
> SELECT count(*) as cnt
>   FROM denpyou, denpyoumeisai
>  WHERE denpyou.DenpyouNo = denpyuoumeisai.DenpyouNo
>    AND T_Code = '123456' AND KikakuBangou = 'ABCD-1234';
こちらも実行してみた結果、8 min 3.88 secかかりました。

また、いそさんの指摘された方法
 SELECT count(*) as cnt
   FROM denpyou, denpyoumeisai
  WHERE T_Code = '123456' AND KikakuBangou = 'ABCD-1234'
    AND denpyou.DenpyouNo = denpyuoumeisai.DenpyouNo;
でも 7 min 52.37 sec かかりました。

やはりこれ以上高速化するのは無理なのでしょうか？