Reading through this thread my intial thought is that you're not aware of the ICS and Google+ Photos bug? Even when unchecking, and or deleting photos they still get stuck in the gallery. A simple Google search will come up with multiple reports of this, and many within the Google forums. Google devs have aknowledged the issue and are working on it. I too have used both ICS 4.0.2 on the Galaxy Nexus and 4.0.4 on the Nexus S 4G. Both have the bug, even with newest update of Google+. Why it does this is beyond me. The only fix I have seen is to sign out of Google+ all together, and clear data and cache from the Gallery. It has worked for some users, but not all. Only other way would be a factory reset, and to not sign into Google+.
Hope this helps OP