My Spotify had a new music "Device" listed with a weird name. Frequently the device would be selected and a song I'd never heard of would start playing, with no sound as it went to the rogue music device.
On my Spotify account I could see a new linked application that I hadn't ever setup. I deleted it, kicked out any logins that Spotify allowed me to do and the problem went away for a day or so. Then it magically reappeared!
When I set up my account I did so with my Facebook account. At one point, IIRC, you could have an account created via Facebook but that meant you always had to log in using Facebook. They later changed this to allow you to set a password and use either.
Assuming the worst I secured my Facebook account (password change/revoking access/etc). No luck. What did work was setting up a proper Spotify password. I'd always logged in with Facebook and never bothered changing the password when they added that feature. Once I changed it I could delete the application, kick out any applications, and then it never came back.
Complete speculation: When Spotify allowed Facebook linked accounts to have a separate password, they generated me a password that was "guessable" and someone used it to access my account?