>After having made more tests, even on a simple a:hover and a:visited styles, the hover style has to be defined after the visited in order for the hover to work. This is something I did not pay attention until today as it was in the order for it to work. But, when the order is being reversed, it doesn't work.
>
>This might be related to the browser however. So far, I tested this on IE.

The behaviour is correct and all browsers should give the same result.
If a link has been used and you place 'visited' *after* 'hover' then it will always take precedence.
Conversely, if you place 'hover' last then it will always take precedence over a preceding 'visited' whether or not the link has been used.
Its logical but not intuitive :-}