CiviMail fails to accurately calculate the number of recipients for a given mailing

I've set up a new site and updated to version 4.4.9 before doing our first mailing. I have a mailing group that contains 220 contacts, of which about 12 have no email address, so I would expect a mailing to go to approx 208 contacts. However, when I set up the mailing, CiviMail reports that there are 2 recipients, and when I send the mailing it goes our to just 2 contacts.
No errors are logged.
Sending an email using the non-CiviMail route works as expected, and the emails go out.
I couldn't test this on the demo server as I couldn't reach demo.civicrm.org