Well, no resolution or workaround, but here's the response from support in case anyone else runs into the issue:

"You can actually increase the time response from the OnTime database over to the windows client of OnTime by modifying the "Max Customers Tree Search Results" from 750 which is set by default to 500 or less. This option is currently only available within the actual OnTime 2007 web client under; Tools > System Options > General Settings. This option will also be added to the windows client in our upcoming future releases of OnTime."