Are you using a back to back configuration? I ask because you shouldn't be using publishing rules on a trihomed DMZ. You have to use packet filters to publish services on a DMZ segment using public IP addresses.
I have noticed a similar problem with dial up connections when the connection is first established. Of course, I never had this problem until I used the Security Wizard
What version of ISA Server are you using? Also, there are some reports that certain combinations of external and internal IP addresses can cause problems.