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.