It's true the MPEG bitstream says nothing about playing partial frames. This information really lives in an abstraction above the bitstream, and has probably been lost after encoding.

I think in order to do gapless playback seamlessly, correctly, and transparently, information about the start and end of a song needs to be tied to numbers of samples from the original PCM source and carried along with the bitstream. This meta information might be stored in an ID3 tag, for example, although I'm not aware of such a tag. (The best I could find is a tag to give the length of a song in milliseconds, not quite what you would want for this purpose.)

Then to do gapless playback, after decoding a frame you could throw away the necessary number of samples to align the frame and end up with a precise number -- the same number of samples as the original source.

This requires some cooperation from your encoder to record where the "real" samples are amongst the padding at the beginning and end. I don't know if any encoders will currently allow you to do this.

-v