While working on an answer, I managed to get the photos live tile 'stuck' on a specific photo, which I don't even have on the disk at the moment. How would I reset the live tile to select random photos from my library again?
Yeah, you did it here. If you ever want to go back to the default behavior, you can do this by changing the "Shuffle photos on app tile" option under Settings, which is in the charm at the right hand side.
It's a nice rule to remember that most of the times the settings at the bottom usually act upon the item in the application whereas the settings in the sidebar act upon the whole application.