There is a known issue, described in KB 3056652, whereby search folders may be inactive after a mailbox move from Exchange 2013 to Exchange 2010 (this can also affect moves from Office 365 to Exchange 2010). The KB describes how the issue can be resolved manually, but if you hit this issue with multiple mailboxes then the manual method could take a long time.
It is possible to reset search folders automatically, but this can only be done using extended MAPI. It is not possible to reset a search using EWS or other APIs (there is no access to the folder flags). The attached console program will open the default MAPI profile and process all mailboxes within that profile looking for search folders. Any search folders that are found, but not active (the SEARCH_RUNNING flag is not set) are reset (which will activate them again). The application requires MAPI, and has only been tested using Outlook MAPI (32 bit - it won't work with 64 bit MAPI). Search folders that are already active (SEARCH_RUNNING flag is set) are left alone.
The following shows the output you'll see against a typical mailbox (in this case, no search folders actually needed to be started); some errors can be expected, and the ones shown below can be safely ignored:
You can download the utility here: ResetSearchFolders.zip
The utility was built with Visual Studio 2013, as requires the Visual C++ Redistributable Package for Visual Studio 2013 to be installed on the computer from which it is run. You can find the package here (choose the x86 version, as the utility is 32 bit): https://www.microsoft.com/en-us/download/details.aspx?id=40784