While I hadn't thought about tracking a cleric when we discussed this, I had considered that rangers ought to have studied their favored enemies. In this Clerics. I see no reason why the shifter ranger in this case couldn't identify a holy roller on the spot (after all, and drawing from my own background, preists and nuns are pretty easily identified by their habits) - could be the extra large holy symbol, the language used by the devote, whatever.
Further, I never considered that Favored Enemy has anything to do with Nature per se. IRL, one group can hate another group any number of real or perceived differences or wrongs. I think of Favored Enemy as just ethnic cleansing embodied.