Hi SAElmer,
It sounds like the Search function isn't configured to find all the items for which you want to search.
Right click on Start and click on properties. Click on the Start Menu Tab, click on Start Menu, and click on Customize. Scroll down to the Search section and check every box related to search (not all required for this, but it makes search work better though it will take just a little bit longer to do it - not much longer), but
especially the one that says Search Programs (which is why these items are not showing up). Click OK.
Now go to Start / Search Box and type
msconfig.exe and enter. At the very top of the results should be a listing of programs including, in this case, only this one. Double-click on that program icon and after the UAC prompt (you may need to enter an administrator username and password if logged in as a standard user) it will open and you'll be there. While this shouldn't happen (it doesn't happen to me), if you get an "Access Denied" message, instead of double-clicking, right click on the program icon and click Run as Administrator and that should solve the problem - but again, I don't think this will be necessary.
You could do the same now with
cmd.exe or
regedit.exe or most Vista programs of that nature - or even the Control Panel options like
services.msc.
I hope this helps. If this doesn't work (and it should), then post back and we'll adjust the search settings themselves and rebuild the search index. I honestly don't think that will be required, but if so we'll do it and THAT will most certainly solve the problem.
Good luck!
P.S. I assume you have Windows Search 4.0 (it should have downloaded as an update). Check to make sure. Go to Start / Control Panel / Programs and Features / Installled Updates and scroll to Windows Search 4.0 in the Windows Section (mine came 9/2/09). If it isn't there, you can upgrade to it at:
Windows Search 4.0.