Bram: if you're using a Mozilla-derived browser, you can put something like this in your user stylesheet (i.e. chrome/userContent.css in your profile directory):

A:link {
        text-decoration: underline !important;
}
A:visited {
        text-decoration: underline !important;
}

The same trick should work in other browsers that allow you to use a custom stylesheet, but I haven't yet persuaded Konqueror to like it.