MySQL INSERT si no existe (no usa la clave principal)

1) ¿Puedes agregar un UNIQUE? restricción en (myid, theirid) ? En caso afirmativo, agregue esta restricción y use:

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

e ignore las advertencias de producción (o reemplace lo anterior con INSERT IGNORE )

2) Si no puede agregar dicha restricción (por ejemplo, a veces desea permitir tales duplicados y otras veces no), puede usar esto:

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