ReAL

И так, проблему решил! Как?

Не работало Индексирование файлов, почитал в нете, что должен был быть запущен сервис Windows Search, он у меня не был запущен и когда я пытался его запустить, он мне выдавал ошибку.
Нашел решение проблемы тут! После того как это сделал, заработало Индексирование файлов, соответсвенно и заработал мгновенный поиск в Microsoft Outlook 2010.

Проблема решена и я доволен, а то я уже и переустанавливал Office и делал Rapair - ничего не помогло. Думаю какой-то Апдейт запортил регистр, так как я ставлю ВСЕ апдейты как на Windows так и на Office, мало ли у кого будет такая проблема.