> If that really bothers you then write your own on-disk compression format.
Why? What are you trying to solve here? You're going to have a hard time making a new format that serves you better than any of the existing formats.
The most common solution for instant playback is just to store the sound uncompressed in memory. It's not a problem that needs solving for most games.
ADPCM and PCM are both pretty common. ADPCM for audio is kinda like DXT compression for textures: a very simple compression that produces files many times larger than mp3, and doesn't have good sound quality, but has the advantage that playback and seek costs virtually nothing over regular PCM. The file sizes of ADPCM are closer to PCM than mp3. I should have been clearer in my first comment that the delay is only for mp3/Vorbis and not for PCM/ADPCM.
There isn't a clean distinction between compressed and uncompressed and lossy/lossless in an absolute sense. Compression is implicitly (or explicitly) against some arbitrary choice of baseline. We normally call 16-bit PCM uncompressed and lossless but if your baseline is 32-bit floats, then it's lossy and compressed from that baseline.