Suponho que estás a usar o Vista.... (ou o XP com o Windows Search 4.0). O que queres é aceder às opções de indexação. Ele só procura nos locais que tem indexados.... é um bocado parvo que, quando não encontra aí, não vai à procura no resto do disco, mas é assim que essa coisa funciona. A solução é indexar o(s) disco(s) todo(s).
Em vista:
Painel de controlo -> Opções de indexação -> Modificar .... e o resto deve ser óbvio.