check your indexing settings. The problem is the more you index, the bigger the index file, the slower the search can end up being.
Do these programs have a entry in the start menu to begin with? that in it self should get them indexed. You may need to rebuild the Index from the indexing options->Advanced page(you can start search for index to find it).