I was doing some testing with Safari 4 (on Windows Vista) and noticed that it was running into the z-index issue that's normally fixed by having a wmode attribute. The issue is that Flash was always displaying on top of all other elements. Normally this can be fixed by applying the wmode attribute of either "opaque" or "transparent" to your SWF, however that was already present.
After playing around with the problem for a good bit trying various solutions of applying an z-index to elements, I decided to check to see if I had the latest version of Flash installed. Turns out I was running Flash 10,0,22,54 and 10,0,22,87 is the latest version. Sure enough, after upgrading Flash everything started working as expected.
So, if you're having problems with Flash being overlaid over all of your elements in Safari, try upgrading to the latest version of Flash to see if it fixes the problem.
(To see how things should work, check out http://pipwerks.com/lab/swfobject/z-index/2.0/dynamic.html. If mousing over the menu options is not showing some pop-up elements, then something has gone awry—so try upgrading Flash.)