Problema con email

Primero de todo voy a tranquilizarte, si se tratara de un caso de captura de claves, etc (lo que se suele llamar "pishing"), no te daría un error de acceso, sino que te dejaría entrar perfectamente o te diría que la contraseña es incorrecta (caso de que accedan y cambien contraseña).
Por otro lado, para que te funcione las cuentas de correo (concretamente hotmail) con outlook 2003, necesitas tener instalado el connector proporcionado por la propia gente de microsoft. Sino, es de género imposible configurar cuentas del tipo gmail o hotmail (y que funcionen).
Te dejo aquí el link directo de microsoft office para que te lo puedas descargar e instalar. Si miras más abajo en el propio link, te indica los pasos a seguir para descargarlo, instalarlo y configurar tus cuentas de correo:
http://office.microsoft.com/es-es/outlook/HA102218233082.aspx
Y ahora, vamos al error ese que te da, que es completamente ajeno a que tengas bien o mal configurada la cuenta en el outlook, ya que como muy bien indicas, incluso accediendo a través de web te sale.
Uno de los trucos para que deje de salir ese error y que te vuelva a funcionar tu mail por donde quieras verlo es el siguiente:
1º.- Abre: http://es.msn.com/
2º.- Haz click en "INICIAR SESIÓN".
3º.- Introduce tu cuenta de correo y tu contraseña e Inicia Sesión.
4º.- Una vez que hayas entrado, desconéctate (cierra la sesión).
5º.- Ahora vete a la página de siempre. Por ejemplo: www.hotmail.es
6º.- Deberías poder acceder a tu cuenta sin más mensajitos ni errores. Y si configuras tu outlook 2003, recibir y enviar correos desde ahí sin problemas.
Y ya finalmente, con respecto a tu última pregunta, decirte que el correo de outlook es seguro siempre y cuando tú tengas instalado un antivirus y este controle tu correo.
Como todo en esta vida, tiene la seguridad que tú le quieras dar. Asegúrate de que tu antivirus controle el correo entrante y saliente y ya es tan seguro como puede ser cualquier archivo que puedas tener en tu ordenador.

Por lo que dices es un robo de clave solo eso aunque un poco grabe porque te robaron la clave y creo que por lo que te aparece es la clave de un virus potente mientras tu cambies tu clave cada semana durante 1 mes completo peero exactamente cada semana si el martes la cambias el próximo martes = y el próximo así ok, te explico si lo cambias exactamente cada semana el hackeer se confundirá esto funciona a mi me a pasado y el tonto hacker ya no t epodra hackear porque al aceptar el termio de licencia en el hotmail dice que si cambias cada semana tu clave msn reporta que tu cuenta fue robada y estas advirtiendo de eston por otro lado el outlook es uno de los más seguros pues detecta los virus y no permite que ese correo te llegue.
Cualquier otra pregunta no dudes en consultarme

Y también probaste borrando archivos temporales de internet, cookies, etc, ¿en ambos navegadores?

Comprueba que estás escribiendo la contraseña exactamente, una variación en mayúsculas o minúsculas hace que Hotmail tome la contraseña como inválida. Esto para la página web.
Para Outlook : el mensaje de error es porque no has escrito bien el usuario o la contraseña. Cuando pongas el usuario, pon la dirección de correo COMPLETA. A mi al principio también me fallaba por eso.
Otra posible causa es que estés usando internet para otras cosas, por ejemplo, programas p2p, y tengas el ancho de banda saturado, por lo que no te deja entrar. Lo que tienes que hacer es reducir la cantidad de ancho de banda que dedicas a esos programas.