Parece que você pode conseguir isso com join
com muita facilidade se os arquivos forem classificados.
$ join -a 1 all_test.txt completed_test.txt
test1 Passed
test2
test3 Failed
test4
test5 Passed
test6 Passed
-a 1
significa imprimir linhas do arquivo 1 que não tinha nada associado a elas.
Se seus arquivos ainda não estão classificados, você pode usar isso (obrigado, obrigado!):
join -a 1 <(sort all_tests.txt) <(sort completed_tests.txt )