Just a bit more after some testing.
It appears that we started getting the issue of styles working until we updated the page/post, then they disappeared (even after our hack mentioned above) when in Safari (FF fine). So it looks like we got the bug described here.
Just not sure if we got this bug after doing our ‘hack’ fix, after updating WP to 3.3.1, after updating TinyMCE Advanced to 3.4.5, or if we just had never noticed it before.
At any rate, we installed the TinyMCE Advanced Configuration plugin mentioned in the other thread (not happy about yet another plugin), and it did actually work – styles no longer disappear in Safari. So we now get a drop-down list of JUST the styles we want our client to see (none of the default WP ones). And we even make an entry to limit the formatting choices to only those we use as well. So this is actually better than it was before.
Just hoping the TinyMCE Advanced Configuration plugin doesn’t cause other issues, and that when this whole things gets completely fixed properly, we don’t have issues when updating now.