Ensure you are attempting the search with the proper method
  1. Do not use the Search Orders function under Recent Searches. This method is sticky and will only give you recent orders:User-added image 
  2. Use Sales > Order Search to find your order
  3. Ensure you're searching using the correct date range
  4. Uncheck any options that may be enabled under the search criteria
  5. Clear any user names or sales methods