Sorry for the delay in response...
I've been using bladeEnc to handle my gapless mp3s. Only on stuff that requires it - like Pink Floyd, Porcupine Tree, etc. Otherwise I use lame - which by default does not create gapless mp3s.
I play my gapless mp3s on a Jukebox 3. It works like a charm. However, I understand that the latest firmware upgrade for the jb3 breaks this. Hhmm... I won't be flashing it.
The player needs to support playing the gapless mp3 gaplessly

Either by design or accident. I figure on the jb3 it is by accident or it wouldn't have gotten broken with the new firmware.
I read (somewhere) that the newer lame does gapless better, than before - whatever that means. I may try it.
This is from the bladeEnc manual on using the -nogap switch:
"Gapless Encoding
From version 0.92.5 BladeEnc supports what we refer to as gapless encoding.
You might have noticed that you normally get a few milliseconds of silence in the beginning and end of each encoded track. This is normally not a problem, but when you have encode a record where the songs blends into each other (like Enigma and most live albums) and listen to the mp3s you can hear a short pause or click between the tracks which can be quite anoying.
There are some technical reasons for this which has made it quite hard to solve, but by using a few tricks and allowing a few milliseconds of music to be moved from the end of one track and onto the beginning of the next, we can make sure that we don't get any gaps.
The downside of this is that if you encode two totally unrelated tracks where the first one ends very sharply and the next one begins with silence, we can unwantedly get a short click in the beginning of the second track since it starts with some milliseconds of music that isn't intended to be there.
The sollution was therefore to by default disable gapless encoding and let the user enable it where wanted by using the -nogap switch.
The -nogap switch can either be placed as a global switch, specifying that all tracks should blend into each other or as a local switch if just two of the tracks should blend into each other.
Example:
1. bladeenc track01.wav track02.wav track03.wav -nogap track04.wav track05.wav
Only the transition between track03 and track04 is made gapless, only track04 'steals' a few milliseconds from track03.
2. bladeenc -nogap track01.wav track02.wav track03.wav track04.wav track05.wav
All the tracks are made to blend into each other, taking a few milliseconds of music from the previous one."
I don't know if this answers many questions, such as why mp3s aren't gapless to begin with (I know why), but I thought I'd stop here and save some typing...