Sorry for that hazzle! My story is quite different but exactly the same: my father in law "didn't get around" to do backups and lost his HDD full of important photos and documents.
That said: I'm quite sure that there are huge regional differences. Without knowing your country just keep that in kind.
I phoned around several companies. I had a simple first benchmark: either directly speak with a tech savvy person (big plus) or being forwarded to one.
That eliminated already half of them who had more business than tech.
The important thing to look out for in hindsight is their transport standards, i.e. how does the broken disk get to them and how does the rescued data get back?
Be careful of companies who have the potential to take the disk hostage ("we give a quote after first analysis").
Paying per file rescued sounds weird to me because that's not how the rescue process usually works from what I understand.
The company I went with was very upfront about the best and worst case what to expect, etc. They were very transparent about the risks and their process as well.
Nearly all of the critical data was rescued and delivered on an encrypted disk. The key was handed out after final payment - a process I quite liked.
In short: talk to the people and find a way to figure out whom you trust most.