Часто ли запись не может быть найдена? Например, люди вводят название города, а затем, если имя не найдено, вы могли бы дать им альтернативы? Если это так, то я бы вернул страницу 200 с новым полем запроса и т. Д.
Если это веб-сервис, то 404 - это нормально, если все, что вы хотите, чтобы ваш API возвращал в таких случаях, "не найдено". Но если вы хотите, чтобы ваши API дополнительно возвращали другую информацию, то 200 (плюс неуспешный код ошибки и другая информация) - это путь.