This solution was meant for the average user .
That in turn means that you can ask the user to do this or that .
You have to come up with a solution with no user input .

And the "average user" as only a few resources on their LAN :
-PC's that jump on and of all the time
-A cheap NAT router wich maybe supports UPnP

You want a hostcache ? can't , they don't have dedicated hardware
You want a proxy ? can't they don't have dedicated hardware
You want to fiddle with their router ? can't , thing doesn't support it
You want average users to do something more then installing your client? can't , they don't know anything about comps and networks .