Operator Overloading with Interface-Based Programming in C#
Short answer: I think your second assumption may be flawed. Equals() is the right way to check for semantic equality of two objects, not operator ==.
Long answer: Overload resolution for operators is performed at compile time, not run time.
Unless the compiler can definitively know the types of the objects it's applying an operator to, it won't compile. Since the compiler cannot be sure that an IAddress is going to be something that has an override for == defined, it falls back to the default operator == implementation of System.Object.
To see this more clearly, try defining an operator + for Address and adding two IAddress instances. Unless you explicitly cast to Address, it will fail to compile. Why? Because the compiler can't tell that a particular IAddress is an Address, and there is no default operator + implementation to fall back to in System.Object.
Part of your frustration probably stems from the fact that Object implements an operator ==, and everything is an Object, so the compiler can successfully resolve operations like a == b for all types. When you overrode ==, you expected to see the same behavior but didn't, and that's because the best match the compiler can find is the original Object implementation.
Requiring all comparisons to use Equals rather than operator== is not a viable solution, especially when passing your types to libraries (such as Collections).
In my view, this is precisely what you should be doing. Equals() is the right way to check for semantic equality of two objects. Sometimes semantic equality is just reference equality, in which case you won't need to change anything. In other cases, as in your example, you'll override Equals when you need a stronger equality contract than reference equality. For example, you may want to consider two Persons equal if they have the same Social Security number, or two Vehicles equal if they have the same VIN.
But Equals() and operator == are not the same thing. Whenever you need to override operator ==, you should override Equals(), but almost never the other way around. operator == is more of a syntactical convenience. Some CLR languages (e.g. Visual Basic.NET) don't even permit you to override the equality operator.
We ran into the same problem, and found an excellent solution: Resharper custom patterns.
We configured ALL of our users to use a common global pattern catalog in addition to their own, and placed it into SVN so that it can be versioned and updated for everyone.
The catalog included all patterns known to be wrong in our system:
$i1$ == $i2$ (where i1 and i2 are expressions of our interface type, or derived.
the replace pattern is
$i1$.Equals($i2$)
and the severity is "Show as error".
Similarly we have $i1$ != $i2$
Hope this helps. P.S. Global catalogs is the feature in Resharper 6.1 (EAP), will be marked as final very soon.
Update: I filed a Resharper Issue to mark all interface '==' a warning unless it is comparing to null. Please vote if you think it is a worthy feature.
Update2: Resharper also has [CannotApplyEqualityOperator] attribute that can help.