The issue is resolved. The root cause was that my local Outlook OST file did not have a copy of all the emails on the server. There is a setting in Outlook that controls how many emails on the Exchange server are actually downloaded to the OST file. In my case, the setting was configured for the last 3 months, so only the emails from the last 3 months were in the OST file.
When searching in Outlook, it was searching for emails on the server (and not just my local OST file), and that explains why FLP could not find the email, because the email was never present in the OST file in the first place, so there was no way FLP could index it. I have changed the Outlook setting to download ALL emails from the server to the local OST file, and now FLP is able to find all emails. The specific option I used to download all emails from the server to the local OST file is called 'Mail to keep offline', and is documented by Microsoft here:
To summarize - This was an issue with my local OST file, and not with File Locator Pro :)