MySQL INSERT se não existir (não usando chave primária)

1) Você pode adicionar um UNIQUE restrição em (myid, theirid) ? Se sim, adicione esta restrição e use:

INSERT INTO mytable (myid, theirid) 
  VALUES (5, 1) ;

e ignore os avisos de produção (ou substitua o acima por INSERT IGNORE )

2) Se você não pode adicionar tal restrição (por exemplo, às vezes você deseja permitir tais duplicatas e outras vezes não), você pode usar isto:

INSERT INTO mytable (myid, theirid) 
  SELECT 5, 1 
  FROM dual 
  WHERE NOT EXISTS
        ( SELECT *
          FROM mytable
          WHERE myid = 5
            AND theirid = 1
        ) ;