Beh, è semplice, togli i bordi e visualizzi quello inferiore nella pseudoclasse hover:
codice:
<style> 
a {
  border-width: 0;
  border-style: solid;
  border-color: red;
  text-decoration: none;
}

A:hover {
  border-bottom-width: 1px;
} 
</style>