Troubleshooting Outlook 2010 AdvancedSearch method

Hello Experts

I am searching for emails in Outlook 2010 from Access 2010 VBA and want to use the AdvancedSearch method.
I know that the email I am searching for exists because I can see it in the Deleted Items folder. However, after at least 30 minutes of searching, AdvancedSearch hasn’t yet found it. The AdvancedSearchComplete event hasn’t yet fired (or if it has I haven’t detected it) and the search result set is empty. After this time, I find it hard to believe that sheer slowness is the problem.
Some more details:

1.      All the action is occurring in the Access class module for my email management form. In the form’s module header, I declare a WithEvents reference to my desktop Outlook instance, which I check is up and running, along with some related stuff:
Private WithEvents molApp As Outlook.Application      ‘ in class module header
Private mblnIsSearchComplete As Boolean   ' set True when email search completes
Private molNS As Outlook.NameSpace
Private molFldrBase As Outlook.Folder
Private WithEvents molFldrInbox As Outlook.Folder
Private WithEvents molFldrDeleted As Outlook.Folder
Private WithEvents molInboxItems As Outlook.Items
…

2.      In the Form_Open event handler, I set up the necessary references, first to Outlook, which I check is up and running, and then to key email folders:
  Set molApp = GetObject(, "Outlook.Application")  ' will raise error if not already running
   mblnIsSearchComplete = False
…
   Set molNS = molApp.GetNamespace("MAPI")
   Set molFldrBase = GetOutlookBaseFolder(molNS)  ' instantiate base folder using value(s) in Control table
   Set molFldrInbox = molFldrBase.folders("Inbox")
   Set molFldrDeleted = molFldrBase.folders("Deleted Items")
   Set molInboxItems = molFldrInbox.Items

3.      I have an event handler for the AdvancedSearchComplete event:
Private Sub molApp_AdvancedSearchComplete(ByVal SearchObject As Outlook.Search)
   If SearchObject.Tag = "LostSearch" Then mblnIsSearchComplete = True
End Sub

4.      I am searching on the BIllingInformation field of the email, which for the email in question contains the text “Deleted;4256” without the quotes.

5.      The search parameters are (checked via the immediate window):
a.      strFltr has the value  "urn:schemas:contacts:billinginformation" LIKE '%4256%'
Note that the value actually contains the single and double quotes shown. Adding enclosing quotes would only confuse things.
b.      strScope has the value '\\myfirstname.mylastname@nhs.net\Deleted Items'
Again, the single quotes are literally present and not just setting off a string value

6.      The actual search which doesn’t seem to want to terminate is kicked off by
   Set molSearch = Outlook.AdvancedSearch(strScope, strFltr, False, "LostSearch")

Any ideas what could be wrong? I’d be interested to hear if anyone else has used the Outlook AdvancedSearch method successfully from Access.

Yours hopefully

Kiwi_731