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.