Is Outlook connecting to an Exchange server or POP3, etc?
Have you verified all the email addresses of those contacts?
Can the user send to EACH contact indvidually without problems?
My first thought is that there may be an issue with one of the contacts' email address, though generally that would prevent you from even sending if connected to an exchange server. Not so sure about POP3, IMAP, etc.
If it's not one of the contacts, could you provide some more information about your email server?