Just cyanoacrylate glues natural rubber very strongly. For reasons obscure to me, the bond doesn't break under rubber elongation.
Try other solvents instead of toluene. Isoalkane mix is sold as a general solvent and paint thinner. Petroleum, turpentine, hexane. Alcohol and acetone dissolve it too, but do they make chemical changes? The right consistency must be rather thick, hence with much solid dissolved.
Yes, solvent glues do dissolve the parts' surface, which tells why cleanliness is less vital for them, and why they are often efficient. I used straight acetone on ABS, without dissolving some plastic in advance, and it works nicely.