We study experimentally the rheological behavior of carbon black (CB) suspensions in water at different ionic strengths and concentrations. We show by means of standard rheometry completed by local magnetic resonance imaging-rheometry that these suspensions first appear to be thixotropic yield stress fluids: they exhibit a yield stress increasing with the time of rest, their apparent viscosity decreases under shear, and a viscosity bifurcation occurs around the yield stress, the fluid evolving either towards stoppage or to steady flow at a large shear rate for a small stress change. Then, an original effect appears when we follow the mechanical state of the material in the solid regime by measuring its apparent elastic modulus at small deformation during a creep test under various stresses. In contrast with various other yield stress fluids for which the elastic modulus under small deformation appears to be constant for any deformation in the solid regime, for CB suspensions, this modulus widely increases while deformation increases up to yielding. We suggest that this strain stiffening effect finds its origin in the specificities of the (van der Waals) interactions and of the (rough) structure (aggregates) of the particles: the slight relative rotation of particles in contact due to deformation would, on average, tend to increase the net area of contact between particles, which stiffens the whole material structure. This is supported by the observation that the relative increase of elastic modulus is approximately proportional to sample deformation, whatever the material characteristics (ionic strength, concentration) and whatever the deformation history.