Your suggestion doesn't really solve the problem though. Either I have dust which is too small to send without combining it with another input, in which case I would still have to do that and compromise my privacy to send to this new service, or my dust is large enough to send on its own, in which case I can just do that but send it to a mixer or instant exchanger or something similar. I don't see the use case for a service where I have to send my dust, as I'm either losing my privacy or losing my coins (or both) to use it.

I've spoken before about Peter Todd's Dust B Gone proposal, which would do exactly as you are describing but without the requirement to first compromise your privacy by sending him your dust. Unfortunately, the demand for such a service would be too small that the anonymity set of people using it would also be too small to be useful.