I don't notice a difference between listening to my MP3s on my Sansa M250's and my Nokia 520 Windows phone. They are all encoded with LAME.
What headphones have you gotten that have helped with fidelity? I'm using Etymotics ER4Ps. Reputed for fidelity (I think), comfortable, durable as hell, expensive (but to me, well worth it).
Sorry I've taken so long to reply, I've not been well recently.
The headphones I had at the time were Sony MDR-EX300 which at the time were a huge upgrade soundwise. For only £40 they rivalled the sound quality of over ear cams that cost over £100. I'm sure yours are better than these were.
Interestingly enough the more recent Sansa Clip+ was hailed by many as having decent fidelity compared to most for a very reasonable price.
I'd say it was close to the particular Sony model, but I preferred the Sony's sound characteristics overall. hat's not to say that any Sony you get will have the same kind of quality. I'm very dubious about buying a Sony after they changed their sound signature. My current NWZ-A829 is the latest one I've heard that I'd be able to recommend.
Talking of varying sound quality between devices, I've heard varying quality on the same device. I have a compact mini system that offers MP3 playback from both a CD and from a USB port.
The quality of the decoder and audio path coming from the CD was vastly superior to the USB port. If you used the USB port there would be no point encoding your files above 64Kbps.