il primo caso è più formale e si usa se poi si prosegue dando del "Lei".
Il secondo è amichevole e solitamente si prosegue dando del "tu"

Gentile, come ti e' stato suggerito, e' la piu' usata. Comunque, mi permetto di suggerire alcune alternative. Personalmente userei un 'Carissima' e nome -gli inglesi lo fanno anche quando rispondono alla risposta ad un annuncio di lavoro (scusa il gioco di parole)

Per il Ms...mi associo con altri colleghi: non credo esista in italiano una distinzione. Se esistesse, pero', non credo verrebbe usata anche a causa della legge sulla Privacy secondo la quale non si e' piu' obbligati a mettere lo stato civile sulla carta di Identita' quindi specificarlo, magari sbagliato, potrebbe suonare come un 'voglio farmi gli affari tuoi', credo.

Mi permetto pero' di aggiungere che, per quello che ne so, in Inglese britannico non si usano nome e cognome insieme...o si mette uno o l'altro, almeno questo e' quello che mi e' stato insegnato.