die Farbe der Unterstreichung allein kannst du nicht ändern. Du kannst aber einen ähnlichen Effekt mit Rahmen, deren Farbe du über border-color modifizierst, erreichen.
Jein - man kann das a-Element auch in ein span-Element verfrachten (oder umgekehrt) und unterschiedliche Schriftfarben verwenden um einen entsprechenden Effekt zu erzielen. Mit CSS3 wird das wohl auch mit ::outside funktionieren, ohne dass man ein zusätzliches Element einfügen muss.
Nachtrag:
<span><a href="http://example.com">baz</a></span>
span {
text-decoration: underline;
color: green;
}
a {
text-decoration: none;
color: red;
}
span:hover {
color: red;
}
a:hover {
color: green;
}
oder
<a href="http://example.com">baz</a>
a::outside {
text-decoration: underline;
color: green;
}
a {
text-decoration: none;
color: red;
}
a:hover::outside {
color: red;
}
a:hover {
color: green;
}
Beides nicht getestet.