"Notice: Running scheduled proc search_indexer..." and make sure it is not immediately followed by any errors. search_indexer is a scheduled proc that will run every 30 seconds by default. It queries the table search_observer_queue and will try to index all objects referenced in there.
Have a look into the search_observer_queue table if there are still entries in it.
Try with another package, e.g. notes (that worked last time I looked). Insert a new item and make sure that immediately afterwards it added an entry in the search_observer_queue.