It's analogous to the operation of those lawyers asking a few thousand euros for unlicensed use of pictures. That's legit as well here. Legal reverse GDPR extortion. Gives us insight into these customers, who've given us power of attorney or we sue. Lose and pay our bills. Win and we are done and the customers pay a much smaller fee (a person, but hopefully adding up to a reasonable fee).
Please correct me if I'm wrong but I think your costs are broader, include attorneys fees, and are therefore different from US costs. In US courts the prevailing party defaults to including costs when preparing the judgment order (parties do almost all of the drafting in US courts) but "costs" is taken to literally mean court costs as in filing fees and a very limited menu of closely related expenses such as costs pertaining to service of process, court clerk photocopying charges, and the like.
Things I'd need (as someone protected by GDPR):
1. strong privacy guarantees on your side
2. transparency about the process and techniques used
3. regular feedback
4. attention to data brokers, but also to anywhere else my pii might be on the internet, which could include shutting down e.g. old accounts on random shops
5. visibility into hacked data dumps (like haveibeenpwned, but for arbitrary information)
I'm pretty sure my information is spread all over at this point, but I'd like to get a handle on how big that spread is and to contain it wherever possible. I'd like to have an idea of how hard it would be for someone with some partial info e.g. a phone number, to determine my name or address.
This kind of service is something that I'm looking for now. I suspect that something like this already exists in "reputation management".
I'm surprised some privacy-focused angel (they must exist) hasn't already done this. If I have $10M to play with this would be a great way to spend it for the public good.