You can use DAV syntax with the LIKE operator and the wildcard "%" and
the AdvancedSearch method to return a Search object with a Results
collection that can be iterated to harvest your returned messages.
That would work with Outlook 2002 or later.
You can set up an filter in the UI for the search you want and then
read the results in the SQL tab. To do that, open View, Current View,
Customize Current View and click on the Filter button. Define your
criteria in the Advanced or Query Builder tabs and then go to the SQL
tab to see how the filter look in DAV syntax. Then look at the Object
Browser Help for AdvancedSearch to see how to complete the search
string with folder and traversal settings.
If you don't see the Query Builder tab in that dialog you can create a
registry entry at HKCU\Software\Microsoft\Office\10.0\Outlook\ named
QueryBuilder. That is a new registry key and it doesn't have any
values, just creating that key is enough. Exit and restart Outlook to
use the new registry key.