After some research and further testing, I found out that Nova uses Laravel Scout by default for searching. I'd assumed incorrectly the default method was a direct search of the database. In our case, our Scout Algolia setup has is very specific for the frontend. For example, we don't include email for security. Also, our local testing Algolia setup has a limited set of records. This was causing intermittent search results when testing.
The best solution here is to setup Algolia correctly to support Nova. But as a quick solution we can disable Scout on a Nova resource level:
public static function usesScout()
{
return false;
}