Yeah, interesting that Vorbis would be faster than MP3. I always thought (I'm not a programmer) that Vorbis is just complex/slow by design and you can't help it.
Could the MP3 decoder you tested also be optimized to beat Vorbis?
I also noticed Vorbis is significantly slower when encoding (with Foobar). With MP3 and AAC it varies, but MP3 is mostly faster.
EDIT: Also something else I later saw on my graphs is that with Vorbis the CPU usage drops on the silent parts of the track (like with FLAC). Whereas this doesn't seem to (noticeably) happen with AAC and MP3.
On a lot of phones, particularly older ones, the main CPU doesn't decode built in audio formats like MP3 and AAC, but rather its done by a slower but more energy efficient coprocessor or DSP core. Are you sure those tests are even measuring the performance of the Mp3 decoder and not just how much busy-waiting the CPU is doing while the music player app waits for the DSP to finish its part?