GSPlayer does a great job on streaming MP3 (and Ogg, too, if you can find it.) The one to download is gsp186a_eng.zip. You also might want to download gsgetfile004.lzh.
There's no installation routine; just copy the appropriate files to a folder on your Axim and create a shortcut to the executable.
Lot's easier than the Windows Media Encoder approach.