I checked back at the gcc/glibc that were built earlier (27 April 2009). These seemed to get built correctly with the right host parameter. So what changed? The rpm and redhat-rpm-config rpms were the same as in April. And yet we see a different behaviour.
Normally, the host parameter that we see while manually building is armv5tel-redhat-linux. While right now we see it is armv5tel-koji-linux. So most likely koji is substituting the _host rpm macro with its own version, and while doing so it neglects the -gnueabi suffix. And probably it was included in one of the latest versions (We use koji trunk on fedora-arm)
Thankfully, there is a configuration option to override this through kojid.conf. Fixed it on all the builders.