I have to query ~10000 gameservers through an UDP protocol to check if they are online on a server every 15 minutes. My code is working, but servers that are offline block threads slowing progress down enormously. I use 20 threads, more will cause the UDP sockets of Python to slow down to a crawl.
Currently I'm using a five second timeout before deciding that the server is offline. Can this limit be further reduced, or must it even be upped?

Please don't suggest using heartbeats, my server is an unofficial masterserver for a game which has to leech and doesn't recieve most of the heartbeats.
You don't have to use synchronous communication (i.e. send packet, block and wait for results), especially not if you're using UDP. Just have one thread send out pings, and another one constantly receiving pongs on the same socket. If you have to do complicated processing with the results, you may want to use another one for that.
The challenge will be in the sending logic - you don't want to overwhelm your own internet connection, so I'd suggest a configurable rate of packets. Also, UDP packets can get lost in the network, so resend at least once or twice before giving up. As a timeout, I'd suggest about 2 seconds, because if a ping to game(i.e. highly delay-sensitive) server takes any longer than that, it's probably not usable anyway.
What is a reasonable timeout for checking if a server is online?