Fax. Definitely fax. It's legislated to be equivalent to a certified letter, and cheaper, and you don't have to walk to the post office like an animal! headdesk

(Did you know it's a criminal offense in Germany to have your fax "participant ID" set incorrectly? The one transmitted in-band, that you configure on your fax device, not the network provided caller ID.)