Parov Stelar - The Princess
The video comes from Sin City, the music is not. I saw the original Sin City, which, if memory serves, was a grim little tale.
I kind of guessed where the video came from, just from the look and feel of it. Then we get the sign for Basin City (2:37) and it was certain.
Parov Stellar has appeared hear before, though it only had one L that time.