Hola Daniel,
La diferencia es muy sutil y depende tanto del hablante (en función de su país y registro lingüístico) como del contexto. Yo, por ejemplo, no uso jamás la primera opción, sino la segunda.
Voy a intentar explicártelo con un verbo equivalente, que es tener
Ya sabrás que DEBER + VERBO = TENER QUE + VERBO
Debería pensar más en ti = Tendría que pensar más en ti.
Lo que nos lleva a tus ejemplos.
Tenía que haber dicho. Tendría que haber dicho.
En el primer ejemplo se presenta una situación de certeza. Por ejemplo, tú sabías que tenías que decir algo, pero no lo hiciste.
En el segundo ejemplo se presenta una situación de duda. Por ejemplo, tú no estabas seguro de qué decir y no dijiste lo correcto.
De todos modos, en el primer ejemplo, tenemos el verbo deber en ya imperfecto, expresando el pasado; no es necesario el infinitivo compuesto. En el segundo, sin embargo, deber está en condicional y el aspecto temporal sí que se lo da el infinitivo compuesto.
Pongo un ejemplo que intenta plasmar lo todo lo anterior.
- Nos has hecho quedar muy mal en la reunión, ya te recordé que el cliente era muy exigente con los plazos. Tenías que haberle dicho que tendríamos el proyecto listo en dos semanas, no en un mes.
- Lo siento, me confundí.
En este caso un jefe recrimina a su subordinado por haberle dicho al cliente que el proyecto iba a estar listo en un mes, cuando en realidad el plazo era de dos semanas. El subordinado le contesta que se confundió y dijo un mes en vez de dos semanas.
Aunque, como he mencionado anteriormente, yo no hubiera empleado esta estructura sino esta otra: "Nos has hecho quedar muy mal en la reunión, ya te recordé que el cliente era muy exigente con los plazos. Tenías que DECIRLE que tendríamos el proyecto listo en dos semanas, no en un mes." Entonces el subordinado contesta: "Lo siento, me confundí. Tienes razón, tendría que haberle dicho al cliente que el plazo sería de dos semanas"
Espero haberte servido de ayuda. un saludo.