I also noticed something strange when removing it with CleanMyMac (similar to AppZapper). There's a separate dock icon file for Spotify, and removing it restarted Dock.app. I think that might be to cover up Spotify running in the background somehow.
If you are running MacOS X Lion, then the OS might keep the underlying OS process around in case you start it again -- this is by design. I have not been able to observe this personally, however.