Se vuoi la transizione solo in uscita devi spostare la transition sulla regola all'hover, così:

codice:
.classe-link {
background: #FFF;
}
.classe-link:hover {
background: #000;
transition: background .4s ease-in-out;
}
Il concetto è che devi applicare la transizione che vuoi alla regola da cui "parte", potresti metterla anche su entrambe volendo per avere la transizione sia in uscita che in entrata.
Comunque si assolutamente nessun problema su Safari ne Chrome ne Opera, solo IE dal 9 in giù non lo supporta.

Ciao