You really only need to fully discharge once every 20 or so cycles is the rule of thumb I'm seeing now.
Couple issues, are you using highr capacity NiMH ir the newer low self discharge? The higher capacity (>2100mAh) obtain that higher capacity at a tradeoff. They tend to have a thinner insulator which causes faster self discharge and is more fragile. Some of the worst batteries are the 2500mAh but then there are some like the sanyo 2700mAh's that were released after the low self discharge and have some of that chemistry in them and they seem to be decent. Sanyo Eneloop (200mAh low self discharge), RayOVac Hybrid (2100mAh Low Self Discharge), Maha Imedion, uniross hybrios, etc are some of the newer technology which not only hold their charge better but are tested out to 1000 cycles.

Charger can make a big difference and just because a charger is called a smart charger doesn't mean its all that smart. I had bought a $30 RayoVac PS4 charger a few years back which was a smart charger but started having short life from my batteries to the point I'd have to carry that charger around and top them off before using them. I got tired of that fast and stoped using NiMH for a while. Couple years later I started reading about these new low self discharge batteries and wondered if my charger would work with them so I started researching it. Turns out it was a known bad model (PS4) which never really put more than 75% of charge on the batteries. I had two or three other chargers before that, some simple trickle chargers, others so called smart chargers. I got rid of them all and bought a $40 Maha c401fs and ran my batteries through a slow charge on it, discharged them in a fashlight and slow charged them again. I put a few in our digital camera and it jumped from 50 pictures to 250 pictures from some old 1600mAh batteries. I bought a set of sanyo eneloops and started reaching 500 pictures on a charge.
A year later I bought a maha c9000 for $60 and started testing my batteries. I dug all the old ones out of my drawer and found the Sanyo's from 1999-2001 that were 1500-1600mAh rated were testing around 80% of that rating. Some 2000mAh rayovacs from 2004 or 2005 tested around 80%. Radio shack and energizers were all under 50%. This was early in 2008 when I bougth the charger so I had batteries from 7-9 years old that were just at the end of their useable life (80% is a general rule of thumb) even though they had not been well taken care of. I went and bought several packs of eneloops and replaced all my old batteries with them. I now run the refresh/test cycle ono the c9000 once a year and record the capacity so I can see how well they are doing.

Hopefully my post wasn't too long and your still reading but to sum it up if you buy cheap batteries and chargers then you can't exect great performance. Just like any other tool, you can buy a $5 china mart knife but can you expect to be great? I probably spent way more than $100 over the years on cheap chargers to not have them work well, its far less expensive in the long run to buy the better ones up front.