The first time I cleaned the heads on my HD100, I waited until I started having problems with a tape. I had 177 drum hours when this took place and it took 4 10-second intervals to clean the heads to my satisfaction.

As a preventative measure, I feel that doing a single 10-second pass every 25-30 hrs would be a good preventative measure.

I'm using the cheap Sony Premium tapes so I don't know if that makes a difference.

How often do you guys clean the heads? Am I overdoing it?

I don't think you're overdoing it. I run a head-cleaner everytime I start a new job or every 10-15 tapes. I use the JVC head cleaning cassette, but have used a Panasonic one in the past without issue.