Creo que el error esta desde el diseño de la tabla, no veo el caso de hacer el campo direccion un atributo compuesto puesto que un cliente solo tiene un mismo domicilio fiscal, aunque puedes tener otros domicilios de sucursales, tiendas, etc. Las tablas auxiliares que tienes (direcciones y ciudades) las tienes que gestionar directamente al editar el registro del cliente.
El ejemplo que mencionas 2 clientes en la misma calle, no tiene problema ya que lo que identifica al registro es la combinación (cliente,calle) esa tabla deberá tener como llave compuesta esos dos campos para que no permita meter mas que un cliente y calle diferente, pero aceptar 2 clientes con la misma calle. Esto no tiene problema en código pues al tratar de insertar un cliente con una calle que ya tiene asignada te saltará la excepción proveniente del motor de BD. Es decir programa tu código como si todo fuera a salir bien y solo coloca un try..except para capturar esa excepción (un cliente con una calle que ya tiene asignada), así no tienes que hacer chequeos adicionales por código.
Las tablas de relación normalmente deben tener una llave compuesta que no permita incluir registros duplicados pero para un mismo registro principal, es decir. Supongamos el ejemplo de teléfonos:
un cliente puede tener n teléfonos, la llave candidata seria cliente+teléfono para evitar duplicados
sin embargo puede darse el caso de que un mismo teléfono sea compartido por mas de un cliente (diferentes razones sociales, nombres comerciales, etc.), la misma llave nos funciona porque nos permitira poner un mismo teléfono siempre y cuando el cliente sea distinto.
Para buscar a quien pertenece un telefono basta:
Código SQL
[-]
SELECT CLIENTES.NOMBRE, TELEFONOS.NUMERO FROM CLIENTES
JOIN TELEFONOS ON (TELEFONOS.IDCLIENTE=CLIENTES.IDCLIENTE)
WHERE TELEFONOS.NUMERO=9999999 # este sería un parámetro
Espero te sirva