If you assume that he rolled a 20 on that check, he still had to have a +18 to make the check to see Pippin's tracks; that sets a minimum level significantly above level 5.
Devil's advocate says hi:
8 ranks + 4 Wisdom + 3 Skill Focus + 2 Synergy with Search + 2 Synergy with Knowledge (Nature) = +19 Survival on level 5.