MP3 Plugin working
I've finally managed to get hold of a VS1011e MP3 decoder chip, so I've been able to construct and test my lettuce MP3 player plugin:

I've written a quick test program to prove it works, this plays an MP3 file which is streamed over ethernet from a PC. The main difficulty seems to be buffering; while the ethernet connection is more than fast enough to supply the MP3 stream, the VS1011 can only accept a limited amount of data at a time, so any extra data that is received needs to be stored somewhere until it is required.
So far, I've had good results playing MP3 files upto 128 Kbit/s using a 200 byte buffer in the PIC's internal RAM, streaming from a PC on the local network.
Microchip have just released a new version of their TCP/IP stack: TCPIPStack 4.16. One of the new demo applications is an "Internet Radio", which plays MP3 streams from the internet using a VS1011e chip! Looking at the code, it seems that they are using an external 32 Kilobyte SPI SRAM chip to buffer received data before sending it to the VS1011e. I suspect that buffering becomes a lot more of an issue when playing streams over the internet, because of the higher latencies.