In new relic transaction logs, I was seeing some PHP requests last as long as an hour. It turns out that time spent waiting on sockets doesn't apply toward max_execution_time, and loops that involved waiting on sockets could end up taking a really long time without timing out.
PHP docs have this to say about max_execution_time:
"The set_time_limit() function and the configuration directive max_execution_time only affect the execution time of the script itself. Any time spent on activity that happens outside the execution of the script such as system calls using system(), stream operations, database queries, etc. is not included when determining the maximum time that the script has been running. This is not true on Windows where the measured time is real."
The solution ended up being setting request_terminate_timeout in php-fpm.