Das Problem ist gelöst.
Es handelt sich offensichtlich doch um ein Problem des Microsoft Internet Explorers.
Für alle die es interessiert hier ein möglicher workararound:
Der innere DIV erhält zunächst nur den mouseOver-Handler.
Wenn dieser aufgerufen wird, um den HTML-Inhalt des inneren DIVs zu ändern wird nicht mit 'innerHTML=...' der Inhalt geändert sondern mit
'outerHTML=...' der Inhalt und das DIV selbst verändert und zwar so, dass der innere DIV diesmal statt dem mouseOver-Handler den mouseOut-Handler erhält.
Und siehe da, egal wieviele Verschachtelungen: alles funktioniert Prima.
Danke an Salokin, der sich mit dem Problem auseinandergesetzt hat und mir diese Lösung geschickt hat.