The trick is to use a CssClass, and apply the CSS only to the hyperlink (the "a" elenent) and not to the surrounding HTML table that ASP.NET uses to show a menu item. Here's a self-contained code sample illustrating the behavior you're looking for:
<%@ Page Language="C#"%>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" >
<head runat="server">
<style type="text/css">
.notSelected a
{
text-decoration:underline;
}
.selected a
{
font-weight:bold;
text-decoration:none;
}
</style>
</head>
<body>
<form id="form1" runat="server">
<div>
<asp:menu id="myMenu" runat="server">
<StaticMenuItemStyle CssClass="notSelected" />
<StaticSelectedStyle CssClass="selected" />
<Items>
<asp:MenuItem Text="Test (selected)" Selected="true" NavigateUrl="~/Default.aspx"></asp:MenuItem>
<asp:MenuItem Text="Test (not selected)" NavigateUrl="~/Default.aspx"></asp:MenuItem>
</Items>
</asp:menu>
</div>
</form>
</body>
</html>
The underlying cause of this problem seems to be how browsers handle multiple conflicting text-decoration styles defined in different CSS classes applied to the same A elements, and perhaps also how browsers handle inheritance from a parent which also has the same styles applied. (ASP.NET's menu controls use CSS classes under the hood to define "inline" styles like the font-underline "attribute", and they apply the same styles on the A elements as the parent elements too. Take a look at View Source HTML emitted by my sample above, or by your code, to get a better idea of how it works.)
I stumbled upon the nested CSS trick somewhat by accident, as I was trying to narrow down the causes of the problem. Seems that if you apply CSS to only the A elements, combining works better. You can probably deduce, by experiment, the underlying rules by doing a View Source on the generated HTML and selectively varying styles of CSS classes applied to each element.
You can also try to decipher the CSS spec for how inheritance and conflicts work with CSS classes, but I suspect experimentation will be easier. :-)