I am using Joomla 1.5.x but I think this works in earlier versions also. In the default theme I made a new menu in the default template (rhuk_milkyway) and the border does not show up. To fix this go to Extensions--> Module Manager--> Select your problem menu --> Advanced Parameters section--> put '_menu' without quotes in the modules class suffix field. Voila!
The picture on the left is before and the one on the right is after the fix