Are all the options in Search Settings on or have you turned off any of them?

Regardless, typing: "cmd" should show a way to start it because of the two ways in which it finds it (cmd.exe is in system path and also in App Paths). What is the exact term you are typing? If you have turned off "Search the system path" it won't show you cmd until you type all three letters.
You are right in your observation that Classic Start Menu's search works differently from Windows 10 Cortana Search or Windows 8.1 Start Screen search. It does not have the ability yet to type the EXE name to have the shortcut shown in search results. In Classic Start Menu 4.3.0, typing the EXE name will return the EXE if it is in the path, typing the shortcut name will return the shortcut.