Using Office Interop AdvanceSearch API method to query a Outlook folder isn't returning all the results, it's only returning results from 2 days ago!
This code been running fine for over 2 years why is it failing now, and only failing on one machine?
Turnsout the it's a new machine after the last one died a couple of days ago, and this lead me to the answer - Indexes...
The indexes hadn't finished re-building from the last retore point, and if you use API before the Indexes are built you might not get all the results.
If you dig into the Indexing Options it even tells you this, shame the API can't surface this warning.