The overlapping of non positioned elements is not specifically defined in the specs (iirc) but usually the one that follows later in the html will go on top of one before if there are overlaps.
However, in your case this didn't happen because the #nav_menu_bg had opacity applied and I guess the browser treats this as more important because opacity applies to the parent and all its children as a whole. It's not inherited as such. The elements are all rendered and then opacity applied to them as a whole which is why you can't cut it off on inner elements - hence the need for your negative margin trick.
If you had added opacity:.99 to your #nav_menu then I believe it would have overlapped as you wished (opacity:1.0 means no opacity so does nothing really).
However, you are then leaving things to chance and expecting browsers all to behave the same. Therefore by adding position:relative and a higher z-index you avoid any mistakes a browser may make and control the situation yourself.