佐々木といいます。

> CagetoryA、CategoryB について、インデックスを使用できない
> でいることが、クエリが遅い原因だと考えています。
何故そう思いました？

> Categoryは、9種類あり、それぞれ、2〜8種類の値が入ります。
レコード数が10万なら各 Category のカーディナリティ値が低すぎますので、
FULLTEXT 以外のインデックスは複数の項目から構成されているものと仮定します。
（一つの問合せで使用できるインデックスは一つだけですから）

その上で、純粋に SQL だけで解決するなら・・・。

SELECT ID FROM Recipe
 WHERE MATCH (Title, Description) AGAINST('+"じゃがいも"' IN BOOLEAN MODE)
   AND ID IN (SELECT ID FROM Recipe WHERE CategoryA = 4 AND CategorB = 2);

MySQL のオプティマイザ次第ですが、
副問合せを利用すれば両方のインデックスが活用できます。
（MySQL 4.1 以上）

はしけむさんの案１のように、
全 Category を文字列として結合したキー項目を一つ用意して、
その項目にインデックスを作成するという手も有効です。
副問合せの部分が速くなると思います。
この場合 FULLTEXT じゃなくて INDEX の方ですね。

また、全文検索だと該当レコードが膨大な数になる可能性が高いため、
LIMIT 句等を使用して取得レコード数の上限を制限する必要があるでしょう。

とりあえず、全文検索と通常の検索を切り離して、個々に検索時間を計測し、
遅い方の SQL を EXPLAIN 等でコストを見つつ、許容範囲内に収まるよう、
データベース環境を含め調整していくのが良いのではと考えます。
それから上記のような形で２つの SQL を結合してはどうでしょうか。

尚、私の環境は senna のMySQLバインディングを
無理やり MySQL 5.0 へ埋め込んだものなので、ネイティブの
全文検索機能と結果が異なる可能性があります。:-)