This might be due to failing UDP Host Caches.
There are only a few GWebCaches left, it seems, and the UDP Host Caches don't seem to work well enough
But for this problem Phex has its own GWebCache set up, which ensures that Phex' will always find other Phex'