Hola, te pongo un ejemplo que yo uso para envío de correos SMTP y no tengo problemas a ninguna cuenta, te aclaro que yo en el valor de smtpserver en lugar de dejar "smtp.mail.midominio" lo cambié a "localhost" porque no enviaba nada y me trabajó bién:
No olvides el Imports System.Web.Mail.SmtpMail
Dim Mensaje As New System.Web.Mail.MailMessage
Mensaje.To = "alguien@hotmail.com"
Mensaje.From = "yo@midominio.com"
Mensaje.Subject = "Mensaje de prueba con SMTP"
Mensaje.BodyFormat = Mail.MailFormat.Html
Mensaje.Body = "<html><body>Este mensaje es para avisar de las pruebas de correo con <b>SMTP</b></body></html>"
Mail.SmtpMail.SmtpServer = "localhost"
Mail.SmtpMail.Send(Mensaje)
Mensaje = Nothing
y ni un solo problema!! espero te ayude