How can I find out if someone really holds a doctoral degree? We're currently interviewing candidates at my company and I'd like to verify if some of them really have the academic degrees they claim. One in particular claims a doctoral degree from a German university.

I've contacted the university, and the dean wrote back saying that they could not provide this information without the written consent of the individual.

I found this policy rather odd; I would have thought that the granting of a doctoral degree was public information. Is this normal? Is there anything else I can do to find out?

I obtained from the library a copy of the thesis in question but it was in German. I also found through Google a spreadsheet which appears to be a list of dissertations published by that university, but it is unclear whether these are doctoral dissertations or not. The person in question and his dissertation are in that list.
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.