What you are seeing is a bug in the multi-line text editor. To my knowledge, the problem also existed to the 2000 version, but not in the 2006. I do not know about the 2004 version. There is a solution, it may not be a great fix, but it is a fix. It uses the MTEXTED variable in AutoCAD and it's this variable that tells AutoCAD what to use for a multi-line text editor. Simply change the editor to be used to something other than the internal ACAD editor and you will be able to edit the underlining as you wish.
This link provides the very simple process to change the editor. Changing it back is even easier if that is what you wish to do.