If you cannot search e-mails neither fom Outlook or OWA then you have problems in the database's index catalog. To fix it on a single server you can use the following article: http://technet.microsoft.com/en-us/library/aa995966(EXCHG.80).aspx
But if you have databases in a DAG you have to do something else:
1- Suspend all replica databases;
2- Follow the directions described on http://technet.microsoft.com/en-us/library/aa995966(EXCHG.80).aspx;
3- Delete the Index Catalog on Replica databases;
4- Resume the replica databases.
To check how the process is going do the following:
1- Open Reliability and Performance Monitor (perfmon.exe).
2- In the console tree, under Monitoring Tools, click Performance Monitor.
3- In the Performance Monitor pane, click Add (green plus sign).
4- In Add Counters, in the Select counters from computer list, select the server on which the mailbox database you want to monitor is located.
5- In the unlabeled box below the Select counters from computer list, select Full Crawl Mode Status in the MSExchange Search Indices performance object.
6- In the Instances of selected object box, select the instance for the user's mailbox database.
7- Click Add, and then click OK.
8- To make easier to monitor the Full Crawl Mode Status, right-click on graph screen then Properties.
9- Select Graph tab.
10- On View Combo box select Histogram bar and Maximum Vertical Scale insert 2, click OK.
When you see a bar for a database it means that the index catalog is been created (value 1), if you don't see a bar meens the indexing has finished for that database.