What is the opposite of :hover (on mouse leave)?

The opposite is using :not

e.g.

selection:not(:hover) { rules }

If I understand correctly you could do the same thing by moving your transitions to the link rather than the hover state:

ul li a {
    color:#999;       
    transition: color 0.5s linear; /* vendorless fallback */
    -o-transition: color 0.5s linear; /* opera */
    -ms-transition: color 0.5s linear; /* IE 10 */
    -moz-transition: color 0.5s linear; /* Firefox */
    -webkit-transition: color 0.5s linear; /*safari and chrome */
}

ul li a:hover {
    color:black;
    cursor: pointer;
}

http://jsfiddle.net/spacebeers/sELKu/3/

The definition of hover is:

The :hover selector is used to select elements when you mouse over them.

By that definition the opposite of hover is any point at which the mouse is not over it. Someone far smarter than me has done this article, setting different transitions on both states - http://css-tricks.com/different-transitions-for-hover-on-hover-off/

#thing {
   padding: 10px;
   border-radius: 5px;

  /* HOVER OFF */
   -webkit-transition: padding 2s;
}

#thing:hover {
   padding: 20px;
   border-radius: 15px;

  /* HOVER ON */
   -webkit-transition: border-radius 2s;
}

Just use CSS transitions instead of animations.

A {
    color: #999;
    transition: color 1s ease-in-out;
}

A:hover {
    color: #000;
}

Live demo