I reproduced that in Internet Explorer 6.
From the tests I've done, I think the ONLY links that setting will affect are those where the webpage doesn't specify a style for the links.
For example, try your underline vs. not underline settings on this page:http://wave.umd.edu/
On that page, the "Always/Never/Hover" setting actually works, but it doesn't work on more sophisticated pages with style specifications (which will be the majority these days)
If you really want ALL links to not be underlined, you have to override what the page is telling the browser to do. The "Always/Never/Hover" setting, I believe, only changes what happens when the page does not give the browser any information on the appearance of links. There are ways to do this... Firefox with the Greasemonkey extension can do that, I believe, but it will take some setup.