A bunch of small modifiers piled together can quickly add up. That said, I might relegate the 'distinguish race' thing to maybe just +20DC, and 'distinguish type' to +5 - it's really easy to tell the difference between a fire elemental's tracks and a horse's tracks.
Just a suggestion, though - completely off the top of my head. I don't really have much to add to the 'new abilities' side of things.
However, on the 'epic skill results' side of things: there is a level beyond which human skill cannot pass. There are no people in our world of six billion inhabitants who are regularly observed walking on clouds. Simply put, to give someone skill ranks beyond a certain level is to change them into something more than human.
IMC, I'd rule that this was due to constant exposure to positive energy (in the form of healing spells). Other justifications may vary. The fact remains, however, that these things are impossible. 'Balance on water', while it may sound cool, is physiologically impossible.
Or is it? I've seem photos of river lizards running across the surface of water (the Amazonian Basilisk - and this isn't an April Fools Day thing, it was in National Geographic a couple decades ago). Just because a human can't, doesn't mean a modified or supernaturally talented person can't.
So your monk can Balance on clouds. Why not? Maybe he's vibrating his feet a thousand times a second to stay aloft. It's not really magic, just supernatural talent. In similar fashion, why not let someone track a trail past 200 sheep? There could still be a whiff of scent that a delicate nose might pick up, or a particularly deep footprint that the sheep avoided out of fluke, or a scrap of thread lying in the mud, or even a trace of dye on a blade of dew-damp grass from the quarry's trousers - it may seem unlikely, but the truly, spectacularly talented tracker should have no troubles.
After all, I've read eyewitness accounts of an Australian aborigine tracking escaped convicts (about 50 years ago, this was). The tracker looked at the occasional twig, scuffs in the dirt, announced a few hours into the hunt that the quarry had sprained his ankle, and sure enough, they found him soon afterwards in poor shape. It's amazing what humans can do given sufficient training.
And can he defeat Cthulhu's avatar? Depends. Is he sleeping underneath a conveniently-placed yet extremely loose boulder of epic proportions, Wile E. Coyote-style? Good old rock. Nothing beats rock.