Why is it so hard for a decoder/mp3 player to recognize digital (or very near digital) silence at the beginning and end of a song and simply skip it? Just call me naive.

First, because of the way mp3s are encoded, it's never total silence. On the other hand, for the vast majority of the files where the gap makes a difference, there's so much of a square wave involved that there's no reason that it shouldn't be easily detectable, within the span of one or two samples, which is, I think, more than acceptable. Why no one has implemented this in a player I don't know.