Turns out our search filter was too broad.
As you can see, we were using a wildcard in the filter, and the query took a little less than 2 seconds.
However, 2 seconds is far shorter than the Active Directory configured time limit so I couldn't figure out why the error was occurring immediately (not even taking 2 seconds when it failed).
I assume AD must have been accruing the time taken by multiple requests from the same account, and at some point began returning the time limit exceeded error.
To solve it, we modified the search filter so that it no longer included a wildcard. The search then runs almost instantaneously, and the time limit exceeded no longer occurs.