Shenh,
Thank you for your response. I think that anti-clockwise rings are almost certainly causing the problem as the data I am working with is not always very clean. Interestingly, ARCMAP Dissolve does not have a problem with the same data so I am looking at using that in Python instead of ArcObjects. It is a great deal faster than my own ArcObjects code.
Val