I've bought a Sony Ericsson W810i recently. It uses the Memory Stick duo (comes with a 512mb one). Supports bluetooth, mounts as a usb drive (tested on Windows and OS X). Can play .mp3 and .m4a just fine, have't tried .ogg. If you need a new phone and don't mind the storage limit (biggest Memory Stick is 2GB? Maybe 4GB?). I'm still to try it under linux.