I've just done a survey of some high-traffic sites and their text that has links. (This survey does not include graphics that may or may not have underlines, although most followed the same patterns for the graphic was GifText.)

All Links Underlined:
nytimes.com
cnn.com
yahoo.com
ebay.com
amazon.com
oregonlive.com
citysearch.com
aol.com

All Links *NOT* underlined:
msn.com
netscape.com
bbc.com
theatlantic.com

Some Links underlined, Some Not:
USAToday.com has 6 links not underlined out of 81 that are.

This list includes the left, top and right hand navigation on the page. It seems to me that for front pages, you stick with one style or the other these days.

Ross : Link : Discussion Board