should について

文法的には正しいのかもしれません。しかし、地域性があるのかも知れませんが、私の周りにこの表現を使う人はいません。おっしゃる通り、that 節に仮定法「he should have lost his job」(仕事を失うべきだったが、実際には失っていない) という、正反対の意味合いがあるからです。

この点は、絶対に誤解を避けたいです。知り合いが失職したことを話している会話ですから、言葉に気を付けます。なので、次のような表現をお勧めします。

It’s unfortunate that he had to lose his job.
I’m sorry that he had to experience job loss.
It’s disheartening that he lost his job.

この形の文では使われる形容詞によってthat節にshouldが入ることがあります。
ただし、このshouldは省略されることも多いです。
今回の文ではthat節の中が過去の話なので、should haveになっているのだと思います。詳しくは「that節の中のshould」などで検索してみるといいと思います。