I recently upgraded to OS x Leopard, and afterwards noticed that spotlight was failing to find certain applications. It was necessary to delete the index database in order to force reindexing. This is done using the mdutil application.
You can find out what it does by opening a terminal window, and typing:
But, if you just want to straight ahead and remove the index database, open a terminal window, and type the following:
sudo mdutil -E /