Convergent, I'm using only 4 cells. Mainly due to my Maha C204F charger charging in pairs (5th cell would have complicated charging routine). I do plan on using the 5th cell option (yes, it's available out of the box) when I get another NiMH charger.
As Morris mentioned, the quoted flash recycle time is for maximum power flash. The SB800 is a very powerful flash - you will not likely be firing it at full power for every frame, so expect better frame to frame performance under normal use.
When used in daylight, especially backlit situations, the flash has to match the power of the sun to retain a correct exposure - that's where it could challenge the SB800's illuminating power and hence longer recycling times.