Chris,

> To sum it up, it was 5 hours for Squeak to do 2001 
> removeKey's followed by 2001 at:put:'s.  Is this related
> to the 12-bit hashing issue you brought up earlier??

This may be but I find it unlikely. Running a quick benchmark of the
form:

dict := IdentityDictionary new.
max := 2000. "operations"
objList := (1 to: 100000) collect:[:i| Object new].
shuffled := objList shuffled. "so we don't replace them in order"
objList do:[:o| dict at: o put: nil].

toReplace := [
	1 to: max do:[:i|
		key := shuffled at: i.
		dict removeKey: key.
		key := Object new.
		dict at: key put: nil.
	].
] timeToRun.

does the replacement within 275 msecs. Of course I don't know if that
models your case well enough but running a message tally on the
operation will definitely tell you where it's spending the time.

Cheers,
  - Andreas