As they say... it works for me.
Most of the time when I've spotted a missing gapless effect it's been becuase the option wasn't selected in the first place, but occasionaly I've had to force iTunes to reanalyse the tracks by selecting the album, gettng info. setting gapless to No, saving the changes then setting gapless to Yes again.
If, as you seem to imply, the presence of a gap occurs sometimes & not others when listening to the same transition, then perhaps it's not so much a fault with the gapless mechanism per se, but relates to the power saving strategy of the iPod. This will read in data to fill a buffer & then put the hard drive to sleep. It then has to restart the hard drive to read the next chunk of data, before the existing cache is exhausted. How long it will take to bring the drive back up to speed, seek the correct locataion and perform a successful read will depend on many factors, e.g. physical motion of the iPod at the time, how fragmented the data that is being read is etc. There must be an algothim in the iPod that schedules the next disk read in an effort to provide for continuous playback, but also to minimise battery use, but since these cannot be predicted with absolute certaintly it must be possible for it to get it wrong occasionaly. I suspect that with higher bitrates & larger files you increase the chances of there being a problem with this strategy. With this in mind you might expect to get the occasional broken transiton, likewise you might sometimes get a small pause within a very long piece that's unrelated to a gapless transiton or momentry freeze frame during video playback etc. What happens if straight after you notice such a glitch you scan to the last few seconds of the first track? My guess is you will get a smooth transition. Defragging the iPod may improve matters...
tt2