Restricción única que verifica dos columnas en MySQL

Puedes hacerlo con un BEFORE desencadenar de esta manera

CREATE TRIGGER tg_bi_mytable
BEFORE INSERT ON mytable
FOR EACH ROW
  SET NEW.address1 = IF(EXISTS
     (
       SELECT * 
        FROM mytable 
       WHERE address1 IN(NEW.address1, NEW.address2) 
          OR address2 IN(NEW.address1, NEW.address2)
     ), NULL, NEW.address1);

Nota: Dado que está utilizando una versión de MySQL que carece de SIGNAL el truco es violar NOT NULL restricción en una de las columnas cuando se han encontrado filas con la misma dirección.

Aquí está SQLFiddle manifestación. Quite el comentario de una de las últimas declaraciones de inserción y haga clic en Build Schema . Estas inserciones no tendrán éxito.