I am having the same exact issue as you are. The IFeature.Store() method is failing for me also. My client is running on ArcSDE 9.3.1. It is not consistent as you describe in your post. I have a custom class extension for which a routine is implemented to delete or update the polygon object. This same codebase is running fine at other similar installations without problems.
... View more