@Eric ,
Just to clarify, do you receive any error message/warning in execution history? I understand that you have mentioned, the issue occurs randomly, are you facing this issue since the time of provisioning or only after any recent changes?
To begin with, on the Search Service, In the left navigation, click on Diagnose and solve problems
– Checkout the tile highlighted files/troubleshooter recommendations (if you haven't done this already).
I’m not sure on what SKU (pricing tier) you’re using, you may see this doc ‘Estimate and manage capacity of an Azure Cognitive Search service’ – and based on your requirement, scale-up the tier. If a tier's capacity turns out to be too low, you'll need to provision a new service at a higher tier and then reload your indexes.