My research indicates this is due to the EnvTraceProc function calling the function TclSetupEnv for all [array] related trace operations, which deletes the entire global env array and any/all existing array searches with it as part of the process of "synchronizing" the contents of the env array with the actual environment. Therefore, it is impossible to actually use the array search functionality with the global env array.
This bug also seems to apply to Tcl 8.4 and 8.5.
set s [array startsearch env]; # returns OK, s-1-env
array nextelement env $s; # returns ERROR, couldn't find search "s-1-env"