I actually sent them a picture of my passport, and they still denied my account.

Hetzner was widely recommended and I was more than happy to pay a premium for their supposedly-excellent service, but I guess they didn't want my money.

Oh well. Went with OVH instead, and haven't had any issues since.