Long delays on new tickets

I am seeing roughly 15 - 20 minute delays between the time a mail hits
rt-mailgate and the user receives the “you now have a ticket” message.

If I remove rt-mailgate and have it just mail me the mail is nearly
instantaneous, so the problem is not mail turn around time.

Any ideas? The machine shows no load, has plenty of memory, etc.

rt 3.0.7_01, mysql 4, and apache 1.3.29 running modperl with perl 5.8.2.