Thanks for all the feedback (no Eugene, that wasn't too long, in fact I did read all of your post )! Part of the problem could be most of my rechargeables are high capacity. Currently the ones I trust the most are Sanyo 2700mAh, but that's because I only bought them pretty recently. Haven't tried the Eneloops yet but they look promising.

Being used to NiCd I do tend to discharge batteries fully before recharging. Part of the problem could be the "smart" charger, though. I've got about 4 different chargers right now and I'm not really happy with any of them. Have been thinking about getting a better one and probably will very soon. But another issue is that I use much of my portable electronics on a fairly sporadic basis so self-discharge is definitely a problem.