lo mas seguro que sus estilos están entrando en conflicto con alguna otra regla CSS, como ya le indicaron revise si sus enlaces tienen alguna clase o id que los afecte, considere la jerarquía de CSS para su buen funcionamiento...
por otro lado
-moz-outline-style esta fuera de uso es algo precario seguir utilizando eso cuando ya se puede usar
outline:none;
por cierto cuando dice que siguen apareciendo del mismo color... estos son rojos? lo pregunto por que usted esta separando :link de :visited y por mas que cambie el color de :link al ya haber visitado el link este jamas cambiara (haber si me entiendes que hasta yo me revolvi jeje)
Cita: a:link { text-decoration: none; color : #003F93; border: 0px; -moz-outline-style: none; font-weight: bold;}
a:active { text-decoration: underline; color : #FF3300; border: 0px; -moz-outline-style: none; font-weight: bold;}
a:visited { text-decoration: none; color : #FF3300; border: 0px; -moz-outline-style: none; font-weight: bold;}
a:hover { text-decoration: underline; color : #CC0000; border: 0px; -moz-outline-style: none; font-weight: bold;}
a:focus { outline: none;-moz-outline-style: none; font-weight: bold;}