I fully subscribe to everything you wrote. I wouldn't never imagine a general purpose cleaner would be able to clean spotify's internal cache.
I guess that spotify exposes the needed information so that the correct cleaning can take place. With correct I mean only expired content and not any explicitly downloaded music files. Was this your experience with CCleaner?
It's fairly simple to remove all extra files by using adb, but why I need to do this? It's not trivial to do this when you don't have computer with you, and with adb, it's not trivial to control what data is being cleaned. But with adb, you don't need to re-login which makes things a bit nicer. At least the cleanup button should have option to not remove the login information. Improved version would be to have manual button to clean up tracks based on date (preferably when those were listened the last time), and later on, this function should be automated. Also it would probably help a lot if some of the playlists could be set to not store music to disk.
Really annoying part is that trying out new music is the biggest cache spammer, which is just the opposite that it should do. And if you need to clean up spotify every 6 months with 32GB device, wonder if it's even usable with any 16GB device?
I understand that spotify does really want to reduce their bandwidth, but IMO, this in worse case could do the opposite as frequently listened tracks will be reloaded every time cache is cleaned.
Not only it would help to be able to play cached songs when offilne, without the need to explicity mark them for download (at the end they are already available in the device) but also to be able to "download" it from the cache, if available, instead of downloading it again from spotify servers. This would be as simple as turn a cached song into a downloaded one.
In fact, there could be even only one unified storage for all songs cached in the device. As long as the song is available should be possible to play it. There could be only one distinction. Permanently cached songs (the ones explicitly marked as downloaded, which are never automatically removed) and expirable/temporary cached songs (from regular listening, with the LRU automatically removed when space is needed for new ones to keep it below max cache size limit).