Recipient verification converses computation resources, reduces network bandwidth and reduces the amount of user input required for generating email messages that include personal salutations that are matched to the recipient's proper title, style, or honorific. The email addresses are associated with a number of recipients, gender-specific markers in names within a salutation, internal and external data sources using the email addresses (e.g., an enterprise contact server, a social network), and historical salutations to determine whether the salutation in an email message is correct for a given recipient or group of recipients. In response to detecting that the sender has not used an appropriate salutation, recipient verification is operable to suggest an appropriate salutation to a user for approval, or to automatically substitute an appropriate salutation for an inappropriate salutation in various aspects.