This is one of my pet peeves, too, but in my experience the main problem is the toilet paper.
Human waste degrades very quickly, especially when mixed with dirt. Even scuffing a depression to receive poo and backfilling with the dirt works. But NOT if there's paper involved. That's what gets dug up/scattered all over the place. A simple plastic bag in the pocket can be used to bring paper back out.
And while we're on the subject I'd like to point out to All My Sisters out there:
WE are the main problem in the paper buildup department, since for obvious reasons we use more of it than men. Let's get it together, girls!