No local email search when encryption is required
Unfortunately, if encryption is required by your server (this can be checked in Touchdown settings>advanced>security policies) then an Email search will not work on the Android device.
This is a security tradeoff. Android does not have a way to transparently encrypt data written to the database. Hence all data existing in the database is encrypted when the server policy requires encryption, including the strings you want to search in.
This means if a user searches for "foo", since the content of the database is encrypted, foo will never be found. The database is really a full text search engine.
While it is conceivable to store off keywords in plain text and use that to perform the searches, this means the keywords themselves will have to be in non-encrypted form, which can still be a security threat.
Unfortunately this is something which cannot be overcome in the current generation of android devices.
You can search the server, however, for older emails if you have an Active sync connection to an Exchange 2007 or 2010 server. You do not need to have all folders you want to search selected to sync. Server search will search any folder over your selected time period.