It seems very common for them to normally prefer being addressed by their first names (since Mr./Ms. seems to be very rarely used in Academia).
My policy : the first time you contact the person, go with Mr. Doe (or Ms. Doe), but sign with your first name. The latter is a signal that you are OK with a "first name email relationship", from this point it will be so most of the time.
You should follow the traditions in the region where the recipient is located. For an American or Canadian, I would probably follow @sylvain's advice, as that is the usual standard in the US—formal at first, but becoming less so as time and familiarity grows.
However, here in Germany, I would continue to use the greeting "Dear Mr./Mrs." until such time as I was directly invited to use their first name (this would be the same as the "Sie" to "Du" switch).
In Sweden, and I believe other Scandinavian countries, email communication is very informal, and communication is mostly on a first-name basis, even if you haven't met in person previously. I can call anybody by first name, even the CEO or an esteemed professor, and nobody would frown upon. Even students address (or at least should, nothing makes me feel older than somebody calling me Mr T., or worse, Sir) their tutors by their first name.
I'd almost never use Mr/Mrs in an email when writing in Swedish, but I would do it more often if the recipient is foreigner and is not familiar with the small power distance in Swedish companies and universities. However, I'd usually be more formal when the circumstances require it -- applying for a job/grant, or sending official documents, for example.
Pro tip: -- never, ever call a Professor "Mr. Smith", if you are adressing them by family name. Always use appropriate academic titles, when applicable. I'd spare this for associate professors or below, but some academics in the country where I'm from are pretty prissy about this.
Some academics are prideful, and you need to play to their weakness. Gain favour of such people by addressing them with a higher title than they currently have. A certain (then associate) professor which some would describe as "a cerberus in a skirt" was very friendly to me and helped me with administrative matters on a few occasions since I consistently addressed her as "Prof. S.", especially in front of other people.