"SmtpFailedRecipientException: Mailbox unavailable" when mailbox is available

Question

I get this error when I try to send an e-mail to a specific address in my code:

System.Net.Mail.SmtpFailedRecipientException: Mailbox unavailable. The server response was: Unknown user

The code sends an e-mail to two email addresses, mine and my colleague's. The e-mail sends to me just fine, but I get that error when it tries to send the email to him.

I looked around, and basically the common explanation for this error is that the email address is invalid, or their mailbox is full and isn't allowed to receive mail, or there is some setting on the server that is restricting it from receiving an e-mail.

But the email address is able to receive email, I'm corresponding back and forth through e-mail with him right now.

Is there any other reason why this error might occur?

EDIT:

Here's the code, maybe someone can spot an issue. I checked the parameters being passed, all the data is correct:

private static void SendEmail(IEnumerable<MailAddress> to, MailAddress from,
    string subject, string body, string bodyHtml)
{
    var mail = new MailMessage { From = from, Subject = subject };

    foreach (var address in to)
    {
        mail.To.Add(address);
    }

    mail.AlternateViews.Add(
        AlternateView.CreateAlternateViewFromString(bodyHtml, null, "text/html"));
    mail.AlternateViews.Add(
        AlternateView.CreateAlternateViewFromString(body, null, "text/plain"));

    try
    {                
        var smtp = new SmtpClient("localhost", 25)
            {
                Credentials = new NetworkCredential("xxx", "xxx")
            };

        smtp.Send(mail);
    }
    catch (Exception err)
    {
        Elmah.ErrorSignal.FromCurrentContext().Raise(err);
    }
}

Solution

Assuming your SMTP settings are correct this is most probably a case of a server-side restriction...

For example to prevent spam the server only accepts smtp from static sender IP and/or is checking sender IP against MX records (DNS) etc.