I had the same issue, spotify prefs, registry keys, msconfig, startup folder, and 3rd party boot utilities (ccleaner, glary utilities) would not work, or was not able locate the Spotify startup files. Here are the steps if all else seems to not work.
First open Spotify if it is not already running.
(1) Delete the Spotify Icon on your desktop if you currently have one. (Any Spotify shortcuts created before completing these steps will no longer work).
(2) Open task manager (ctrl + shift + esc)
(3) Switch to Processes tab and Right-Click "Spotify.exe" and select "open file location".
(4) In this folder you should see two application files named, "Spotify" and "SpotifyLauncher".
Right click each file and add a 1 to the end of the file name.
"Spotify1" and "SpotifyLauncher1"
(5) Right click Spotify1 and select create shortcut. It should make a shortcut icon which you can drag to your desktop. (This file can be renamed to anything as long as the target is not changed).
Once this is complete, it should no longer load on startup. You can now use the created desktop shortcut to open Spotify.
Hope this helps - IS