Careful deleting the whole playlist as it will only replace the ones that spotify recognizes which may not be all the songs in the list. I lost a lot of songs this way, tho technically it did work. Not sure why Shazam didn't have those older songs from way back when - new phone maybe, but that seems strange. Anyway, try renaming playlist rather than deleting would be my recommendation.
Think I have this figured out. I found that some tracks were being added and some were not. Turns out that if Spotify has more than one match for a track discovered in Shazam then it won't auto-add it to the My Shazam playlist and the "add to" button is also grayed out. I experimented and found this behavior is consistent.