I figured out the problem. I did two things:
Added this to the web.config of the proxy.ashx application:
<configuration>
<system.web>
<httpRuntime executionTimeout="180"/>
<system.web>
</configuration>
This site is also behind an IIS Reverse Proxy which had a request timeout of 30 seconds. So I went to the Server Farm setting on the proxy machine and changed the proxy timeout from 30 seconds to 180 seconds.
Between the two settings it now works.