Sounds like you could use an index on LAST_UPDATE_DATE on both Table2 and Table3. Did you look at the execution plan for the query (both with and without the last line)? Did you see any table or clustered index scans?
This is what the tuning advisor said too with estimated improvement of only 11%. I was trying to avoid creating any more indexes I guess. I built those eventually and the SQL is much faster now. Will see how those new indexes will slow down something else. The execution plan was showing and is showing one instance of the non-clustered index. Now it uses the new index I just built (cost 36%). With a statement like 'date1 <> date2' it will always scan and not seek, right? Thanks for assistance btw.
It depends on how many other rows are returned via the other conditions. If you only have a few hundred rows where STATUS_FLAG IN('I','C') then it may use the index and do a bookmark lookup. Is there an index on that column too?