One possibility is that the Linux getaddrinfo() is thread-safe, but only by way of a lock that only allows one request to be outstanding at a time.
The next step should be to get the getaddrinfo() source code from glibc and see what it does. It's open source, hey. :-)
I can dig around a bit, but I have to figure out what I'm looking for.
On the failure platform, are we sure Python is using the native getaddrinfo, not the Python-supplied one? I've had some fun (not) with the latter; for working on an LSB-conforming version of Python, I can't let it use the glibc version of getaddrinfo because it's not in the spec (will be in the next version); but the Python addrinfo.h header has some fields in different order than the Linux one, and it managed to call the Linux one anyway. The result of that was not subtle, however :-) so I don't think that's the problem that started this thread.
I do know the Linux (or rather, glibc) getaddrinfo doesn't get rentrancy through magic, it calls gethostbyname_r and gethostbyaddr_r. (Note the Python emulation getaddrinfo just calls the straight gethostbyname and gethostbyaddr routines and so is likely not to be reentrant).