Restrição única que verifica duas colunas no MySQL

Você pode fazer isso com um BEFORE acionar desta forma

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);

Observação: Como você está usando uma versão do MySQL que não possui SIGNAL o truque é violar NOT NULL restrição em uma das colunas quando linhas com o mesmo endereço foram encontradas.

Aqui está SQLFiddle demonstração. Remova o comentário de uma das últimas instruções de inserção e clique em Build Schema . Essas inserções não serão bem-sucedidas.