I am in the US and have been using Fastmail for years. I have no problem with automated billing to a consumer credit card. I have recently begun using Hetzner as well, and this also bills to the same card. I just looked at the Hetzner charge, and it shows up in the CC transactions as "hetzner.com" with a US domestic phone number associated.

My guess is that your CC has more strict foreign alerting than mine, so perhaps this is not very helpful information. But it is certainly possible, and perhaps Hetzner billing support (and Fastmail too!) have some advice for how to smooth things over with the bank.