Depends on context, jurisdiction, etc — for example, given topic is US law enforcement, here’s one example of costs of investigation assigned for collection based on outcome of a case:
The way it works is they have a private party perform part of the search, then have that party bill it to you.
Annoying, for sure, but short of them having a your signature acknowledging responsibility for the cost, it should be straightforward to shut down the debt collector's efforts.
Until that debt gets sold to a collector that couldn't give two shits about what is legal