There is a bug in the documentation.  Hash codes are computed based on the field values, and do not treat the ID in any special manner.  Thanks for finding that, I'll make sure the docs get fixed.

With respect to what's happening in the code, you can see the same behavior in Java.  What's happening is that you're mutating an object that already exists in the set, changing its hashcode.  So any further lookups will happen in the new hash location, but the old object is sitting at the old hash location.  Here's a java program that illustrates the same thing:

import java.util.*;

public class MutableTest {
    static class Value {
        String v;

        @Override
        public int hashCode() {
            if (v == null) return 0;
            return v.hashCode();
        }

        @Override
        public boolean equals(Object o) {
            if (o instanceof Value) {
                Value other = (Value)o;
                if (v == null) return other.v == null;
                return v.equals(other.v);
            }
            return false;
        }
    }

    public static void main(String[] args) {
        Set<Value> s = new HashSet<Value>();
        Value x = new Value();
        x.v = "hello";
        s.add(x);
        x.v = "world";
        s.add(x);
        System.out.println("size=" + s.size());
    }
}

A better way to have a data structure that guarantees uniqueness with sobjects is to use a map.  Apex makes it easy to generate such a map from a query:

Map<ID, Opportunity> m = new Map<ID, Opportunity>([select id from Opportunity]);

Rich