DexNav'ing for Egg moves is actually a very common practice, it's one of DexNav's features. It applies to all the Pokemon you can find using it, which is usually Pokemon you can capture in the wild while walking.
So basically, any Pokemon that you can DexNav can have an Egg Move on it. Keep in mind though, this Egg Move is random, and the DexNav informs you which moves it has.
Hope I helped!