Back in the days when I was playing with electrolysis, there were two ways for me to get carbon electrodes -- the carbon rod from a D-cell dry cell (you can't find those much, anymore) and the graphite lead of a mechanical pencil. Both were gradually attacked at the anode, roughening and pitting the surface, the battery rod affected faster than the pencil lead. The cathode remained just fine the whole time.
I know in the "cartoon chemistry" books we all read, as kid or on-line, that carbon doesn't react with the oxygen released or with the common, cheap electrolytes, but something's happening. The carbon may be oxidizing, inefficiently, but still oxidizing. There certainly have to be binders within these rods, that may be affected, unless you're using pure graphite crystals, which sounds ridiculously expensive for your application. Or perhaps, simple mechanical action of the release oxygen gas is fraying the rods surface (and no I can't explain why that happens to the anode and not the cathode, in that case.) Or why it happens only in base and not in magnesium sulfate.
At any rate, one of the problems with industrial generation of hydrogen by electrolysis is the expense of the platinum electrodes, and the general lack of an alternative. Recently, some college made a big deal about a recent discovery, they have an alloy for the anode, containing aluminum, if I remember correctly, and a cost-effective way to recycle the anode, after it's oxidized. I don't think they would have made such a big deal about it, if this wasn't a problem plaguing industry right now.