I provided three pieces of evidence: a link to my Essex University staff page; a reminder that I paid my £75 renewal fee using a credit card that has DR RICHARD A BARTLE on it; my driving licence number, so they can see that the DVLA uses my title.
I suspect that none of these will work, because they will doubtless only accept actual original documents, even though they're unlikely to know what an Essex University PhD award certificate looks like (answer: awful). I therefore enclosed a covering note telling them to use Mr in the event that they want a certificate, as no way am I trusting that to the post.
I was also required to send a photo. They have a neat system now where you can go to an authorised passport-taking body (Snappy Snaps in Colchester has sufficient gravitas to count as one) and they'll give you a code that you can tell the Passport Office to use to retrieve your photo. They also give you physical photos, too. This is a scan of mine:
That is exactly how I look after getting off a nine-hour flight, so I'm very pleased with it.