Mike chews me out for including optional operations on an interface

Mike, another dev on the C# took issue (aka slapped me around) with the way my current interface is being built.  He doesn't approve of an Add method that can possibly fail.  He thinks that if the interface declares it then it's something that should be expected to succeed in most cases.  There may be times when it could fail, but having a method be optional and then always fail seems like a bad smell to him.  Because of this he thinks I should refactor the interface into a ICollection interface which presents a non-mutable view over the elements (i.e. Contains, IsEmpty) and a IMutableCollection which extends ICollection and adds the mutating operations.  What do you think about that pattern?  Note: each opreation (Clear, Add, Remove) is independently optional.  So would i need IGrowableCollection, IShrinkableCollection, etc.?  I.e. I might have a collection that implemented Add, but didn't want to implement remove (like a Queue which only allowed removing of the head, not of arbitrary elements).

It seems to me that this explodes the interface hierachy immensely.  It also makes it difficult when you want to take an object that is an aggregate of many interfaces.  You could say:

void Foo<T>(T t) where T : IGrowableCollection, IShrinkableCollection

But this gets pretty unweildy fast.  Anyone have any pointers to work done in this area and the benefits/drawbacks they faced?