Tried a new MP3 player today: SKU34705 from dealextreme. This 11 $ player ships without a memory card, which will cost about another 11 euros for a 4 Gb micro-SD card. The build quality is not great - but I wasn't expecting too much for 11 $. It works however, and there are no cords since the memory-stick, player, and battery all fit in the back. That does make the headphones a bit more back-heavy than the conventional corded Sennheiser PMX I've used before (39.90eur at the local shop, for only the headphones!). The battery is charged from the USB-port, and the SD-card shows up as a disk-drive in Ubuntu automagically without installing any drivers.
Hope the flu is finally defeated now. 6 k at something close to 5:47/km today did not feel too bad.