In the case of Steam, it uses an indicator and displays an icon too big if an appropriate one is missing from the icon theme (fixed by adding one at the right size). With Clementine, it's an indicator too, though the fix is specific as you pointed out. I'm not sure if SpiderOak uses an indicator or the systray.
In any case, the fact that some apps fetch a big icon and display it as is isn't right: the indicators applet and the systray applet should check the size of the icon loaded and resize it if it's too big. It would not fix specific issues like Clementine not using the user theme but it would at least display something usable.
This has made me do some actual thinking: SpiderOak works both ways - when it sits in the systray it scales properly, when displayed as an indicator it is unscaled. If you also consider all the other non-scaling indicator applications, the Indicator Applet is now the obvious culprit. I have changed my previous post to reflect this revelation.
Everybody go here and state your case (or at least click the "Affected" option):