Ein wesentliches Feature von IMAP (und ich nehme an Du verwendest dieses Protokoll) ist, dass man nur die gewünschten Email-Inhalte auf Klick automatisch herunterlädt. Zunächst sind da nämlich nur die Betreffs.
Nun lässt Mail.app aber leider die Suche auf dem Server vermissen, d.h. um Emails suchen zu können, müssen sie lokal auf dem Rechner liegen.
Dazu muss man Mail.app anweisen, alle Emails stets herunterzuladen. Diese Einstellung ist bei mir (SL) unter Accounts/Erweitert und erläutert unvollständig:
Kopien der Emails behalten, um sie offline bearbeiten zu können.
Sollte sich Mail.app diesbzgl. irgendwann seit 10.6. gebessert oder geändert haben, möge man mich bitte korrigieren.