Your search criteria must be an exact match and is case sensitive.  For partial searches, use the  asterisk character as the "wildcard" (shift+8 on your keyboard).

For instance if your have an order STORE-0000012345 and you want to search using 12345 then the proper string to enter on the order ID field is *12345. You can also search for partial names, emails, etc. For instance if you know the persons email contains mike and is at gmail you could enter *mike*gmail* to perform a wildcard search.