Verifique si existe, si es así, actualice por 1 ++, si no, inserte

Dependiendo de cómo esté estructurada su tabla, es posible que pueda usar ON DUPLICATE KEY UPDATE (enlace al manual de MySQL) característica de INSERT :

INSERT into new_mail VALUES ('$to1', '0') ON DUPLICATE KEY UPDATE message_number=message_number+1