Calling sendmail directly (also from a shell), causes the same problem: Delay for about a minute. The -q switch doesn't help.
I've noticed that sending mail to my an address at the same server that my PHP is running, works just fine.
Using Pine also works fine, to all addresses.