You really need to explain the circumstances to us better .
Redhelen is assuming that an heir-hunting company contacted you out of the blue and said they believed YOU were due some money in a will. In those circumstances, one has to sign a binding agreement to get them to tell you who has left you some money.
From what you said, I don't think is the situation - I think you are acting on behalf of the deceased, either as executor or a solicitor is doing it for you (always expensive and unncessary unless the affairs of the deceased are really that complicated).
A beneficiary in the will cannot be found, and YOU have hired an heir-hunting company to trace them. After a week, you decided to cancel that contract (for reasons you haven't explained here).
These companies typically work on a 'no find, no fee' basis, a bit like the ambulance-chasing lawyers, however if you cancel their services before they have had a chance to find the beneficiary, then they have very likely incurred cost but had no chance to get a return back. In such circumstances, it is most likely that a term in their contract, if you signed one, allows them a payment.
Over to you to explain the circumstances a bit better, please.