The "fast enough Vorbis" was likely the addition of Tremor, the first fixed-point Vorbis implementation. There's a nice (but with many old entries) chart of decode speeds here: https://www.rockbox.org/wiki/CodecPerformanceComparison

On newer hardware + software, like the Clip Zip, the gap is much smaller and the performance way higher than needed in any case (except for HE-AAC, the clear loser).