Ran into that once with a client with a low end DSL connection in one of their remote offices. The additional latency caused multiple sync retries and the firewall which was set up for an adaptive (i.e. heuristic) response interpreted the constant multiple sync responses as a potential attack and shut off the port for 30 minutes thereby killing the sync. Half hour later the port would be reenabled and maybe sync would (or wouldn't) work for awhile until it started jackhammering repeat replies.
If it were a static firewall rule it wouldn't work at all - so the fact it worked and then stopped is a good indication that it's something other than a static rule at work.
I do know some ISP's get a little pissy if you're hitting their routers a little too frequently and rapidly. So they may also be throttling something or blocking a port.
In an attempt to cut down on junk mailers, one of the big providers in my area now insists on you only using their outbound SMTP servers. I first found out about that policy change when I got a dozen calls one morning from clients who suddenly could receive but not send any mail. Turns out the announcement was buried in the middle of an e-mail the ISP sent. You know. One of those marketing e-mails nobody ever reads?
The good part was that you could get a "waiver" of that requirement from this ISP. But you needed to call them and provide a justification for why you needed to do that first. Interfacing with your employer's e-mail system was usually deemed sufficient reason.
You could try calling the ISP to see if it might be on their end.
