This is the most likely cause of an unexpected failed search. If your search terms include a common "stop word" (such as "the", "one", "your", "more", "right", "while", "when", "who", "which", "such", "every", "about", "onto"), then your search will fail without any results. Short numbers, and words that appear in half of all pages, will also not be found. In this case, drop those words and rerun the search.
See MediaWiki User's Guide: Common stop words for the stop words filtered out by the database. From there one can at least go to a page with a stop word as title. Searching for the combination of one or more words and the common word "not" give a database query syntax error due to a bug in the software.
The searches for "espio", "Espio" and "ESPIO" all return the same results.
You cannot use regular expressions or wildcards such as ? or *. If you don't know what that is, don't worry about it. To search for pages with the words "boat" or "boats" search like this: "boat or boats".
If a word appears in an page with single quotes, you can only find it if you search for the word with quotes. Since this is rarely desirable it is better to use double quotes in pages, for which this problem does not arise.
An apostrophe is identical to a single quote, therefore Knuckles' Chaotix can be found searching for exactly that (and not otherwise). A word with apostrophe s is an exception in that it can be found also searching for the word without the apostrophe and the s.
The search only applies to the main namespace (those pages without "MediaWiki:" or "talk:" or "user:" in front). The main namespace contains pages, indexes and other content-oriented book pages. To search the other namespaces check or uncheck the tickboxes in "Search in namespaces" box found at the bottom of a search results page. Depending on the browser, a box may still be checked from a previous search, but without being effective any longer! To make sure, uncheck and recheck it.
Check or uncheck the tickbox "List redirects" in "Search in namespaces" box found at the bottom of a search results page.
The wikitext (source text, what one sees in the edit box) is searched. This distinction is relevant for piped links, for interlanguage links, special characters (if ê is coded as ê it is found searching for ecirc), etc.
For reasons of efficiency and priority, very recent changes to pages are not always immediately taken into account in searches.