It's quite possible to have the client save all the addresses collected via the "X-Try", "X-Try-Ultrapeer" 0.6 handshake headers, and maybe pongs.

Write them to a file in the application directory; use that list again the next time to get connected.

With a list of say 1000 hosts, you shouldn't have a problem getting connected, without even knowing the address of a dedicated host cache.

(It would surprise me if no client does this right now!)

There is still the problem of the initial connection after downloading. So, just supply the app with a huge addresses file, or just the addresses of some dedicated host caches.