Some applications don't pop up in the search even when you type in their name. Take for instance Sushi. When you type in "sushi" into the search box, it fails to throw up the application. Only when you type in "gnome-sushi" does it appear. This is despite the fact that the application has "sushi" by itself in the application description. There are other applications which don't spring to mind right now, but I've discovered before.
They are hidden because they are marked as technical packages - the ones with no .desktop file (see How does Software Center determine what is a "technical item" and what isn't? ).
You can use Show # technical items link in the bottom left corner to see them.
Some packages are not the name of the application itself. Take the example of the "Sushi" application, it was meant for Gnome and thus the package itself is prefixed by "gnome-", furthermore, it is a technical package and in order to see them in searches you must click the "Show X technical packages" button down in the bottom-left corner of the Ubuntu Software Center window.