Such a service would be able to charge a (low) fee, for example for a kind of API subscription, but would not be a money transmitter in any way as it's not at all involved in the creation of transactions.
This doesn't resolve the issue. You're still required to place trust in the service to provide you with accurate information. There are still security concerns, just like previously.
This would make a JoinMarket-style CoinJoin network possible where users could participate with their SPV wallets (Electrum, Sparrow et al.).
The problem (and feature) of JoinMarket lies in takers covering the costs of inputs and outputs for their makers. When selecting an entity to mix coins with, I'm essentially covering the expenses for their inputs and outputs. This quickly renders it unappealing in the present context, where we pay more than 15 sat/vB.
What's required is a network with no distinctions between makers and takers, that consists solely of users leveraging the network to create a shared space, because the main problem with coinjoins is being online at the same time with the other joiners. Once a collective of participants is created, they could merge their inputs, generate blinded outputs, and cover only their respective portions of the costs. I believe this network is feasible to create. Fidelity bonds could still serve to discourage sybil attackers.
Instead of a central server holding this info (which could draw legal and security concerns)why not let the users themselves manage their UTXOs in a peer-to-peer manner?
Sybil attacks. By selecting random users, you're essentially relying on the assumption that an attacker doesn't control all of them and inject their inputs. While you might think your coins have been successfully mixed, the attacker would still be aware of your outputs.