I compared all the parameters and they are the same. If I copy and manually move the where to the end after the outFields the request works. It is definitely an issue with the rest API as the parameter order shouldn't matter. I would watch him do it and see if there is an order to how he is doing the search to see why the requests are in a different order in the first place (that might be a browser issue?)
Sorry I'm not much help, but the order of the url parameters is what is causing the issue. I would report that as a bug to technical support and try to find a workaround until the bug is fixed.