I personally would use such a service if it provides enough hints to be trustworthy (e.g. a long existence). Of course this kind of service would have to target specifically privacy-related usag. But as the blockchain is public and it's easy to deanonymize oneself (e.g. publishing an address somewhere in social media, not doing proper wallet "management" with tools like Electrum) this "legal" mixing segment should be big enough.

An interesting addition for such a service would be a "trustworthy" chain analysis feature, where the user can enter the affected addresses/UTXOs and the mixer already providing a stance about the probability of the funds being frozen. Such a service should however restrict "marking" and "freezing" funds to clearly (=proven) criminal usage like recent hacks.

I could also imagine a "tiered" logging policy, where instead of freezing a log is kept (only!) in the case of coins of dubious origin, and the time until this log is deleted depends on the risk related to the coins. The user would then be able to use the coins after mixing them but dubious coins would still be possible to be tracked.