В Internet Explorer (я тестировал во всех v6 - v9) граница в подменю сначала не появляется, когда вы наводите курсор мыши на текст. Во второй раз при наведении курсора он отобразится. Он отлично работает в Firefox и Chrome - то есть всегда отображает границу. Я разместил пример страницы на моем сайте .
IE (при наведении):

FF / Chrome (при наведении):

Здесь нет ничего необычного, некоторые css, onmouseover / onmouseout Javascript для установки style.display = block / none. Я придерживался некоторых идей из этого ответа на аналогичного вопроса .
Я сократил ее до минимума, чтобы попытаться найти проблему, но все равно не повезло.
Элемент ul подменю имеет отображение: на нем ничего не установлено. Похоже, что IE не беспокоит рисование границы, пока не будет установлен display: block, и не рисует ее изначально, когда Javascript используется для отображения элемента.
<html>
<head>
<title></title>
<style type="text/css">
ul, li {padding:0; margin:0; border:0;}
ul#hover_menu_list,
ul#hover_menu_list ul {list-style-type:none;}
ul#hover_menu_list li {float:left;position:relative;display:inline;}
ul#hover_menu_list li ul {border:1px solid #000;display:none;position:absolute;left:0px;top:20px;width:170px;}
ul#hover_menu_list li ul li {display:block; clear:left; float:left;width:140px;}
</style>
</head>
<body>
<ul id="hover_menu_list" onmouseout="document.getElementById('menu1').style.display='none';" onmouseover="document.getElementById('menu1').style.display='block';">
<li>
Menu
<ul id="menu1">
<li>Submenu1</li>
<li>Submenu2</li>
</ul>
</li>
</ul>
</body>
</html>
ОБНОВЛЕНИЕ: Проблема действительно была проблемой типа документа. Добавление в переходный или строгий тип документа устраняет проблему. Связанная страница была обновлена с исправлением.