std::stringで使ってるクラスを、CStringに変えて、CString::Find検索にしたところ、
劇的に速くなりましたｗ

STLって重いんですね。
ちょっとSTLのスレッドでその辺を質問してこようと思います。