Update: I actually checked how well the flash was mounted, and to my surprise, although the tightening lever was deployed and everything, the speedlite WAS slid back in the hotshoe mount, and by quite a lot.
I pushed it back forward like it is supposed to be and suddenly the camera is doing what it should. I set it in TV and selected 1/640th shutter. Took a few underexposed test-shots, and then turned on the speedlite. BANG. The camera overrode my shutter setting and reduced my shutter speed to 1/180th. It worked 3 times, so I am calling this SOLVED.
I feel a little silly, but that is still way better than if there were a major problem with the camera.
On the other hand, I wonder if you could "squeek" a little higher sync speed out of the camera (just 1/250th maybe) by deliberately mis-mounting the flash in the hotshoe.