I have a somewhat similar issue, it will return *some* programs/shortcuts but not all, and not the most obvious ones that I think *should* have been returned. I'm using the search menu *a lot* to start programs, and this bug is annoying to the point that gave up on AtartAllBack and went to the freeware "Classic Shell" instead. It has been like this on all versions of StartAllBack, including in the latest version 3.9.3 (I just checked as I have it installed in a VM).
Example:
1) I type "pdf" in the search bar in the enhanced classic start menu. I would expect "PDFGear" to be on top of the search result, since it's the *only* shortcut in my Start menu that starts with the letters "pdf". But no, instead it returns:
A-PDF Restrictions Remover
A-PDF Restrictions Remover on the Web
cGPSmapper manual (PDF)
Little Navmap User Manual PDF (Offline)
Melodyne 4 Introduction.pdf
Now these are all shortcuts in my Start menu that contains the letters "pdf", but I would expect any shortcut that *starts* wit the letters "pdf" to appear at the very top of the search results, or at the very least to be included in the search results. But neither is true.
2) Only when I type "pdfg" in the search bar in the enhanced classic start menu does this appear in the search result:
PDFgear
PDFgear on the Web
Uninstall PDFgear
This is more than a bit annoying. Search in StartAllBack is broken and cannot be trusted to return the correct results, at least in the enhanced classic start menu.
The same is true for any of my installed applications, with shortcuts in the start menu. It's not logical what is and what is not returned when I search for an application by typing part of its name in the search bar.