I have the same problem. I already rebuilt the Spotlight cache and did a reload and all the other fairy dust things that get recommended. However, they are only temporary fixes or don't work at all, depending on today's weather or some other unknown variable.
Spotlight finds my items immediately, Launchbar finds my items immediately, Alfred 2 worked perfect until maybe two weeks ago (I don't have a good event log, but I'd wager that problems started with the newest version). Now, while I can resort to rebuilding my Spotlight cache, it may or may not help and if I have to do that every day then Alfred starts to look not as attractive anymore. Also, restarting is often not possible as this machine is running complex multi-day calculations frequently.