(This is for developers, primarily for the ones making Media Center, but feel free to chip in if you like this / hate this)
I recently made a high level audio engine in C++ using OpenAL. That's not really important but it sets the scene. We had a bug at one point with gapless playback skipping, and it was only later I realised the precise implications of what was happening to make the bug (at the time I was more concerned with getting rid of it).
To buffer audio continuously without gaps in OpenAL you use a queue of small buffers. When a buffer has been played you pull it off the front of the queue, fill it with audio data, and put it on the end of the queue. Larger total buffer size means less skipping, less cpu usage, and less responsiveness when we wanted to change tracks.
Hm, that tradeoff sounds familiar
What we had accidentally managed to do was to cut into the buffer queue. What this means, in OpenAL at least, is that it would be possible to have a very very large playback buffer, but when you wanted to change what was being played (a track change, or seeking in the current track) you could cut into that buffer, to bring the change about almost instantaneously! (To compensate for the lower buffer and to protect from skipping, you might want to hit the update loop more often than usual while in this phase). Once the change was made you could build up a large buffer again.
This is a best of both worlds option: No skipping, responsive program.
Of course, you probably aren't using OpenAL, and maybe what you're using can't do this. But I thought it might interest you that it is possible in at least one case. Let me know what you think
Disclaimer: I never did rigorous testing into this approach to find out if it had any side-effects, whether it worked on all platforms supported by OpenAL, etc. Don't blame me if you try to do this and it doesn't work / breaks your program!