How can I find out if someone really holds a doctoral degree?

You could ask the candidate to provide written consent for the university to verify his degree. If he refuses to allow verification of his CV, then he's probably not someone you want to hire, regardless of whether his doctoral degree is legitimate or not.

When you get an academic degree from a German university, you usually get two official certificates. One (labeled Urkunde) is official proof that you hold the degree but does not include a grade. The other (labeled Zeugnis) is official proof of your grade but (according to some bureaucrats, though I suspect they just like to make life difficult) not of the degree. I think for doctoral degrees it is common that these two documents are combined into one, which is then also labeled Urkunde, or in this case Promotionsurkunde, but includes the grade. The grade for doctoral degrees is still often in Latin, in which case the best grade is typically summa cum laude, followed by magna cum laude.

A normal practice to make sure applicants actually hold the degrees they claim to hold is to ask for photocopies of their degree certificates along with the application. This timing makes it less awkward to ask for proof. Also, faking a certificate, even if it's only a fake photocopy, is a more serious offence than just lying about a degree, and at that point the reward of this more serious fraud isn't even certain yet. It is also possible to ask for a certified photocopy. I am not sure why this is done; maybe it repels a few more liars.

German universities are in fact not allowed to hand out any data about their faculty and (former) students. I would consider the spreadsheet linked above a weak form of corroboration. Weak because it looks more like someone's personal effort than an official list. (Even two dissertation titles are missing.)

Of course, technically even an authentic doctoral certificate is not proof that the holder of the certificate really holds the degree. There might have been a subsequent revocation for plagiarism.

One factor that may lead to even competent people committing fraud is the requirement of thesis publication. Once all other requirements have been satisfied, people usually get a warning that they are not allowed to use their degree before publication of the dissertation. As far as I know this is done quite consistently because even with the warning it does happen occasionally. Of course this is less of an issue nowadays, as the publication is often done electronically.

(I earlier wrote that standard practice was to hand out the certificate before publication. Some people protested, and I must agree that what I wrote was obviously wrong. It doesn't make sense for universities to hand out proof of something that is not true yet, and they don't do it. Sorry.)

In Germany, a strict requirement for doctoral degrees is publishing your thesis. These are called Dissertation; master theses or similar are not. This is the final step of acquiring the degree.

Nowadays this publication can be online (in which case it should be easily findable), but at the very least should be contained in the university’s library. The library in turn should have an online catalogue allowing you to search for works by your candidate and see whether one of them (usually the only one) is categorised as Dissertation, doctoral thesis, Doktorarbeit or similar.

In your particular case, the library maintains a search engine for theses since 2005 and has lists of theses since 1997, both can be found here. I can imagine that some libraries will tell you over the phone whether they have a thesis by a certain person – this is not private information, as we are talking about a published document and everybody could obtain this information by physically visiting the library.

Getting a thesis listed in those records without actually having a doctoral degree should at the very least require more skill than forging certificates and should be the best proof you can get without asking permission from the candidate to verify the degree. The only exception would be if the candidate lost his PhD, which is however extremely rare and often connected to public attention and also often causes the PhD thesis to be retracted. In any case, also ask for a certificate of all qualifications, as it makes it easier to sue the candidate if it should be forged.

Finally be aware that failing to find a thesis in such a list may have other causes than the person not having a degree. In that case you need to ask the candidate.