I had a quick blast of the example sequences and this is the Acacia so ancient vascular plant. This is not billions of years BTW but could be a couple of hundred million years ago (MYA), probably younger (< 150 MYA). Anyway ... this protein is comprises a repeat amino acid motif (check NCBI), the second "issue sequence" described in the question was close to the size of the repeat locus, but start/stop within a repeat. Thus I don't think the repeat locus is part of the issue.

Genome assemblies I noted the examples you gave were all draft genomes and this suggest the problem was with the original genome assemblies. If this was true the way to overcome this would be to reassemble the sequence using a reference genome, bwa-mem2 type thing. Thus, here the error is occurring way before the sequences is even downloaded.

Reading frame what I think you are doing is performing an alignment in the proteins and then using that alignment as the template which is then transferred to the sequence data. So now the nucleotide data is nicely aligned including all indels. That appears to be the goal of pal2nal. A common error here is reading frame error, particularly at the beginning of the sequence. I use transalign regularly for this purpose and do encounter that error. I don't know how pal2nal deals with reading frame errors so I can't comment, but thats why I wanted to see the nucleotide input to pal2nal to check this.

Trees the reason this is taking place is because iqtree doesn't permit a tree. That I can help with, I know about tree building. If you post your iqtree command as a separate question , together with the iqtree error, I can probably answer that. What I'll identify is how to build a tree, this likely to exclude sequence, or could be addressed as two trees. Dunno, but if the bottleneck is can't build a tree - thats easily fixable. In this case, is the sequence issue an assembly error, reading frame error ... something else. There's not enough data that I could point to as the underlying source.

I had a quick blast of the example sequences and this is the Acacia so ancient vascular plant. It forms a locus within the protein in the first part of the question. This protein is comprises a large repeat amino acid motif (check NCBI), the second "issue sequence" described in the question was close to the size of the repeat locus, but start/stop of the locus is not in accordance with the repeat structure. Thus I don't think the repeat locus is part of the issue.

Genome assemblies I noted the examples you gave were all draft genomes and this suggest the problem was with the original genome assemblies. If this was true the way to overcome this would be to reassemble the sequence using a reference genome, bwa-mem2 type thing. Thus, here the error is occurring way before the sequences is even downloaded. Just to note, repeat structures can often be collapsed on a draft genome assembly, but I don't think thats happened here.

Reading frame what I think you are doing is performing an alignment in the proteins and then using that alignment as the template which is then transferred to the sequence data. So now the nucleotide data is nicely aligned including all indels. That appears to be the goal of pal2nal. A common error here is reading frame error, particularly at the beginning of the sequence. I use transalign regularly for this purpose and do encounter that error. I don't know how pal2nal deals with reading frame errors so I can't comment, but thats why I wanted to see the nucleotide input to pal2nal to check this.

Trees the reason this is taking place is because iqtree doesn't permit a tree. That I can help with, I know about tree building. If you post your iqtree command as a separate question , together with the iqtree error, I can probably answer that. What I'll identify is how to build a tree, this likely to exclude sequence, or could be addressed as two trees. Dunno, but if the bottleneck is can't build a tree - thats easily fixable. In this case, is the sequence issue an assembly error, reading frame error ... something else. There's not enough data that I could point to as the underlying source.