Windows – Outlook 2007: instant search not working

I have tried so many things to try to fix this problem with no results.

The machine is running Windows XP SP3 with Microsoft Office 2007 Standard.

What is happening is that the instant search not working within Outlook. The normal search works without the indexing but the mailbox is HUGE and takes a very long time to search without being indexed.

I have tried all of the following:

• Rebuilt the index
• Reinstalled Office 2007
• Removed the users Outlook profile in Application Data\Microsoft\Outlook and Local Settings\Application Data\Microsoft\Outlook
• Removed the profile from control panel as well (Mail -> Show Profiles -> Removed the profile from here)
• Reinstalled and reindexed Windows Search 4.0
• Disabled all non-essential Outlook add-ons

This mailbox is stored on a Microsoft Exchange 2007 server, not sure if that helps or not.

I have tried other methods mentioned online through many Google searches with no results. Everybody seems to give up and just use the normal search which is really slow.

I will provide any information which will help anyone willing to give me a hand with this.

As requested by @mnmnc