Whenever they dissolve! hehe just kidding. I normally wait for them to fall into little pieces (1/4 to 1/2 inches) to replace them... Just braking into 2 or 3 pieces is not enough to warrant replacement, IMO.
Just squeeze the hell out of it in a bucket of siphoned out water every now and then. I keep one on hand, eventually you'll squish it and it won't return anything close to normal shape - then switch it.
I rarely ever replace them just when they start falling apart. I have several spares but I also use them to help in the setup uf new tanks. take the dirty sponge from the old tank and use it to seed the new tank. then I leave it in the new tank and the old tank gets a new sponge. shortens the cycling time of the new tank imo