Va detto che la frase è arzigogolata e poco credibile. Considerando soltanto la forma, e non il senso, però, rilevo un paio di difficoltà. Il rapporto tra la principale e la completiva è più complesso di quello che sembri, perché è chiaro che la storia sia il soggetto della subordinata, non della principale. Se lo consideriamo soggetto della principale, infatti, la subordinata rimane monca, né sarebbe possibile reduplicare il sintagma: *La storia non mi sembra la storia sia veritiera. Pertanto, rimettendo in ordine gli elementi, riconosciamo che la costruzione sintattica soggiacente è non mi sembra (che) la storia sia veritiera. In essa, la principale è non mi sembra e (che) la storia sia veritiera è una soggettiva.
Un altro problema, solo nominale, riguarda e che riguardava quel signore, che va definita relativa coordinata; ne consegue che che abbiamo incontrato ieri sia subordinata alla relativa coordinata.
Il resto è corretto.
Fabio Ruggiano