Sim, seus múltiplos terminais são o motivo. O histórico do bash é gravado quando você sai do shell, não individualmente para cada comando.
Você pode obter seu arquivo de histórico em ordem cronológica com classificação:
history | sort -k2
Se você deseja que seu arquivo de histórico seja escrito de forma mais contínua, acredito que este post de blog explica isso bem
Eu também encontrei essa pergunta de troca de pilha unix que pode ser útil.