問題とされている環境と状況をできるだけ具体的に詳しく説明してください。 問題とされている Email アカウントの種類を提示してください。 (POP/SMTP, IMAP/SMTP, Exchange などのうちのいずれか )
Instant Search は Index を使用し、 Advanced Find は Index を使用しないための違いだと思われます。
Index を 再生成しなおしてみてください。