Dle popisu by to mělo fungovat tak, že se vyhledávací databáze smaže a pak se znovu vytvoří (v článeku se mluví o řádově hodinách). Takže bych se zkusil zaměřit přímo na službu Windows Search: http://support2.microsoft.com/mats/windows_search/ cs
Po fixu a následném restartu zkus znovu tu reindexaci Outlooku.