Prominent display of the total count of targeted recipients for a mailing prior to "sending" will give users a reality-check and more confidence about their selection of recipients.
When user submits step 2 in send mailing wizard, run a query which calculates the actual number of recipients. Query should take into account: Included Groups, Excluded Groups, Included Mailings... as well as excluding contacts w/ do not bulk mail, contacts without email addresses, etc. (If it makes sense - use (i.e get a count from) the existing query which actually collects the mailing recipients for send.)
Once calculated, the recipientCount value should be available to each form template in the wizard. It should be re-calculated if the user goes back and re-submits step 2 ("Select Recipients").
When $recipientCount is populated, include an additional .tpl which displays a recipient count block in a div (class = messages status") below the step title. Block text is (example recipient count shown):
"You have selected 1,250 contacts to receive this mailing."