Illustrator10から搭載された「エンベロープ」という、テキストを様々な形に変形できる便利な機能があります。
Illustrator10でこの機能を使用している場合、アウトライン化されていない場合でも「フォント検索・置換」の画面では表示されないため、文字化けに気付きにくく注意が必要です。
Illustrator CS以降では「フォント検索・置換」に表示されますので、全てアウトライン化してあるはずが「フォント検索・置換」から表示が無くならない場合はエンベロープが使用されている可能性があります。

エンベロープ中で使用されているテキストのアウトライン化する方法
エンベロープの部分を選択し、 「オブジェクト」メニューから 「エンベロープ」の「拡張」を選びます。