This is really the relevant part of the trace:

> 15:06:53.356337 public.XFree86.Org.www > obelix.premium.com.au.1334: S 2128045057:2128045057(0) ack 1953605146 win 17520 <mss 1460> (DF)
> 15:06:53.356451 obelix.premium.com.au.1334 > public.XFree86.Org.www: . ack 1 win 17520
> 15:06:53.580745 obelix.premium.com.au.1334 > public.XFree86.Org.www: P 1:259(258) ack 1 win 17520
> 15:06:54.890118 obelix.premium.com.au.1334 > public.XFree86.Org.www: P 1:259(258) ack 1 win 17520

The first packet shows that public.xfree86.org is implementing path
MTU discovery.  For path MTU discovery to work, when a router rejects
a packet that is too large, it must generate an ICMP NEED FRAGMENT,
and that packet must get to the end that originated the large packet.

Most likely what's happening is that either your PPP is failing to
generate the ICMP NEED FRAGMENT when it rejects the packet, or a
router in between is eating it.

This is a fairly common problem, and the solution is to implement
what's known as `black hole detection': after we retransmit the large
(1460 byte payload) packet a certain number of times and don't get an
ack, we ratchet down the MSS and try again.

Unfortunately, the black hole detection takes a while (you need
several losses before it kicks in) and may be buggy in some systems.
It's also not implemented at all in some older systems, and some
systems may have ineffective PMTU caches.

The result is what you see: when you try to connect to sites using
these buggy or incomplete implementations, you'll lose completely;
when you try to connect to other sites using PMTU discovery, you'll
get delays the first time (or after the PMTU cache entry for your host
has been GCed).

The only solution that can be applied on your end is to raise the MRU
on your end of the PPP link (and the MTU on the other end), so that
large packets can get through intact.

[Note that NetBSD now implements PMTU discovery, but it is turned off
by default.]