Few Ex-Employees not visible in Search in HRMS Manager responsibility

We have a peculiar scenario in production where we are unable to view some ex-employees when searching in the person screen.

We have around 20 ex-employees out of which about 15 are visible and 5 are not visible.

The security profile attached to the responsibility is based on Payroll. And all the 20 ex-employees are in the same payroll. They were in the same payroll throughout their employment.

Any idea why some ex-employee's can't be viewed where as some are visible ?

Also we have an older clone of the production system. In this system I am able to view all 20 ex-employees. I am not aware of any changes that were done in the setups or security profile etc. Till now I did not find any difference between the 2 systems except in production every month payroll is run whereas in the clones system payroll has not been run since the clone was taken about 4 months back.