Ah - I hadn't taken on board that you were using Outlook 2010. My screenshot is from Outlook 2007.
I suppose also that enabling "search" in the deleted items might not necessarily lead to indexing of items located there.
Looks like I might have shot myself in both feet
No matter, a genuine expert is bound to stop by soon