El mensaje de envío siempre se va a mostrar asi tengas un error en el codigo. Yo particularmente sugiero que uses una libreria como PHPMailer, la cual es muy completa y puedes enviar correos electronicos usando tu cuenta de Gmail.
Aqui te dejo el
link donde puedes descargar esta libreria y otro
link donde puedes ver ejemplos de como usarla.
Me he guiado con ambos y hasta ahora los resultados han sido muy buenos