Really depends on the country and even the people you are talking to (in countries like Canada and the US, profs come from all over the place).
Little anecdote: ten or so years ago, I was department head and had to obtain references for short-listed candidates to an assistant prof position (we hadn't started using mathjobs yet). One of the names rang a bell, but I couldn't quite place it. I sent my emails without paying any more attention. "Dear First Name, X has given your name as a reference and I am writing to request a letter". Emails come back with letters and I realised at that point that the reason the name rang a bell is that it was a Fields medalist (with an email from a different uni than his "canonical " one, hence my confusion). I was happy, because in hindsight, I probably would have agonised a long time on how to start my letter. He replied using my first name and didn't seem one bit annoyed that I wasn't more formal.
In short: don't overthink it. Most profs don't really care.
For a first contact, you can always play it safe and use "Professors X and Y" and see what they use in their answer.