To avoid handcuffing people with types (which is definitely un-pythonic) and maintain backwards compatibility, the standard collection modification methods could be hooked so that if an object of an incorrect type is added, a warning is raised and the collection gracefully degrades by removing mixed-in type information and methods.
-1 to automatic downgrading. Imagine in step C that the collection is auto-downgraded and later in step Q a method is called that no longer exists -- Exception raised. (I find a Warning less than useful -- either you aren't going to use one of the special methods, in which case you didn't need the special container and the warning is just noise, or you do need the special methods and you'll get an exception further on when you try to use it and it's no longer there.)
Personally, I like warnings. When my code passes tests, and I see a warning, often times it clues me in to an additional edge case or subtle bug.
What are the other options? Throw an exception immediately, or don't downgrade at all, then throw an exception when someone tries to use a method that doesn't exist on a child? Throwing an exception immediately forces people to be explicit which is good, but it isn't backwards compatible. Not downgrading at all seems like it could be a source of annoyingly subtle bugs, since it is possible that you could put something in the list that fulfills part of the contract, but not all of it, or fulfills the contract in a subtly incorrect way.
Additionally, a method could be provided that lets the user "terminate the contract" causing the collection to degrade without a warning.
+1 Either it was not needed to begin with, or the need has been satisfied and now we need to add in objects with a different type
Do you have some examples of functions where you pass in a container object and get the same type of object back, but it's a different object?
The restriction on being the same type is not needed. If a list is homogeneous, an iterator or set derived from the list would be homogeneous, and keeping that information in tact would probably be a good thing.
With the slight adjustment, list, tuple, set, filter, iter (+most of itertools), sorted, reversed and heapq off the top of my head. Looking at the list, you could give type decorations legs just by having iterables of decorated objects retain the decoration, and having the basic collection types inherit type decorations at construction.