Sprint Epic 4g Touch, just got OTA ICS 4.0.4. I have two exchange accounts setup on my phone.
I've been dealing with these security pop up messages as well since the ICS update. 
I hope this wasn't already posted and I missed it, but one thing I noticed also was when the "security settings" notification popped up, I could click it, but all it gave me was the "Update security settings" message, then "OK" or "Cancel." Clicking OK didn't do anything except get rid of the message for a minute. 
I just found this, and I guess I will report back in a few days to see if it has worked, but I went into Settings > Security > Device Administrators > 
Then there is a single setting/check box for my Email program, stating "enables server-specified security policies." Mine was already checked, but for grins, I clicked it anyway. It prompted me with another screen, listing all kinds of info about the email app, with an "Activate" and "Cancel" at the bottom. I clicked "Activate," and it did it's thing. The check box for "Email" is still checked, but if I click it again, now I have the option to "Deactivate" instead of "Activate."  
I'm hoping the "security settings" notification is supposed to bring you to this screen, but is bugged and never gets you there. At least, it seems that way for my case.
Maybe it will fix the problem?