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
You would indeed need at least 2 dust inputs to be able to send 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.
Thanks, I was looking for that project but couldn't remember the name.
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.
I wouldn't install software for this, but if it can be integrated as an Electrum Plugin, it could actually work!