Here's another spin on how something soft can wear something much harder. A carbon steel blade used to chip tree limbs will last a very long time happily turning hundreds of yards of fresh cut tree limbs into mulch. Now replace the blade with a new, identical one and feed it only tree tops with lots of large leaves and the blade will dull much quicker.
When the moving blade passes the softer leaves, the leaves can slide perpendicular to the edge of the blade before and as it's being cut. When this rubbing occurs, it dulls the edge sooner that the harder wood that maintains it's shape and is cut by the blade pretty much inline with the path of the blade's edge.
Add some dirt to the mixture and the sliding, rubbing action across the edge of the blade really dulls things up in a hurry.
Since the stylus is sliding past the two sides of the record album at pretty much a perpendicular angle to the groove walls, you have the same dynamics. As other's have pointed out, the actual pressures involved at this microscopic level is quite amazing. Add even a little dirt and its just a matter of time, (or distance - traveling in the record groove - depending on how you want to look at it).
