I have had this problems a few times, and it is a crapshoot - - - sometimes it works, others it just won't... I have fixed it (in asp) by using a regular SMTP server with the username and password for validation. The message you mentioned is usually the other side's fault (your server is blocked for some reason), or is a permissions fault on the server, depending on the source of the information. This is the ASP code snippet that got around that:

    set oNewMail = Server.CreateObject("CDO.Message")
    set MailConfig = server.createobject("CDO.Configuration")
    '2 is for HTML formatted
    MailConfig.Fields.item(cdoSendUsingMethod) = 2
    'The server that you are going to route your email thru and your credentials on that server
    MailConfig.Fields.item(cdoSMTPServer) = "smtp.server.com"
    MailConfig.Fields.item(cdoSendUserName)="username"
    MailConfig.Fields.item(cdoSendPassword)="password"
    MailConfig.Fields.item(cdoSMTPServerPort) = 45
    MailConfig.Fields.item(cdoSMTPConnectionTimeout) = 10
    MailConfig.Fields.item(cdoSMTPAuthenticate) = 1 ' 0
    MailConfig.Fields.Update()
    oNewMail.From = "emailaddress@server.com"  'needs to be the same as the email assigned to this account
    oNewMail.To = "test@test.com" 'can be a ";" separated list of recipients
    oNewMail.Subject = "Web Feedback"
    oNewMail.HTMLBody = msg 'text to send, in this case HTML
  on error resume next
  oNewMail.Send()
  Response.write msg	
  if err.number <> 0 then
      response.write err.number
      response.write err.description
      %>
      <font size="3" color="red">An error occured while sending your email. Please 
      verify your email address is correctly formatted. If this problem persists, please 			  
      email us directly at emailaddress@server.com.</font><br>
      <%
  end if

Hope this guides you on the right direction (I know is not ASP.NET, but you should get the idea).