Assuming the following:
- the old prof is gone for good
- there are no available grades in the system
- the exams went with the prof, and possibly destroyed
- we are talking about last fall's term, so the course has finished and the students have moved on
It looks like a possibly unrecoverable situation. The students did their part, not their problem the tests didn't get marked and they are entitled to the credit and the grade.
To phrase it in a contractual issue, the students contracted with the university for the education and agreed to prove their competence within a specified time period. The university in turn agreed to provide academic credit and a grade. The students did their part, the university cannot demand extra work from the students due to a failing on it's part. That the professor absconded with the final exams is not the student's problem.
I would say that unless it is a critically important course, like "Infectious Diseases 320" or "Nuclear Physics 440" where an incorrect grade could be disastrous, assign a grade near the student's average in other courses. Some students may rightly feel they are entitled to a higher grade, those same students will likely understand the situation and agree to rewrite the final.
Remember that "fair" in many cases is what everyone agrees with. If I think I deserve a B+, and you offer me one based on my semester average (along with a crystal-clear, full disclosure explanation of what happened) I will be ok with it. If I think I deserve an A I may consider wether that grade will actually make a difference and take the B+ rather than rewrite the final.
(and it looks like someone borrowed my assumptions)