Problem: I experienced Spotify being stuck in full screen mode. The title bar with minimize, maximize and close wasn't present and no keyboard shortcut I know about would exit full screen.
Solution:
@mastier has improved the solution - see here
Solution (old):