Also wenn du Outlook in Verbindung mit Exchange im cached mode betreibst, sollten die ÖO mitindiziert werden, denn die Suche funktioniert nur im cached mode.
Allerdings kannst du darin so weit ich weiß nur über die erweiterte Suche suchen, Outlook/Vista search sucht nur in deinem Postfach.
Das empfohlene Tool Lookeen finde ich sehr gut, das durchsucht nämlich beliebig viele Ordner gleichzeitig und man kann die Suche mit wenigen Klicks so einschränken, dass man in 99% der Fälle auch findet was man gesucht hat.