The other issue is that the full name is used in the address, but only the last name in the greeting. There are no apartment numbers in Germany, so the name in the address must match the name on the mailbox. There can also be a lot of "Herr Müller" working at the same address.
In the end I opted for Mr/Mrs/Other + first and last name, and dropped the title. It's good enough for this purpose, but it shows how tricky something like a name can get, especially if the person filling the form is not aware of all this.
To give a bit of context I help people as a courtesy when the information on my website does not suffice. If readers can't be arsed to say hello before they ask for a few minutes of my time, I quietly wonder who raised them. Imagine walking up to a retail employee and blurting out "I need printer paper" without saying "hello" or "excuse me".
This is I think solved with asking how people want to be addressed. It also helps deal with situations where someone's legal name isn't how they are usually referred to.