Mav: Hmmm. Interesting point. Under certain conditions, yes, you can see tracks as they melt from covering snow. The original track compresses the snow into ice; when it's later covered by more snow and then the top layers melt, those tracks are harder and show as raised above the surface.
Of course, in the case of Larry's search, there were so many tracks made by searchers that might not be useful, in addition to the very narrow conditions under which that can happen.
The other point of tracks in snow is they show up very well from the air. I was once able to follow two skiers from a helicopter even after a two day storm had covered their tracks. When they crossed a lake, the smooth conditions showed the underlying ski tracks pretty clearly as differences in shadow/density as the fresh snow settled.
Also, I've seen tracks made in mud -- especially by horses as Mike says -- show very clear and fresh the following spring. They get frozen and are preserved pretty well in the fall. And, of course, there's the famous 3.5 million year old footprints discovered by Mary Leakey and team some years ago:
But, all that said, back to the original question. In normal sand or dirt, a footprint gets pretty fuzzy by about day 3, though still very recognizable.