Morten Nielsen I am having the same issue. In Runtime 10.2.x, if my map service has a limit of 1,000 features, that 1k will be returned, but when it has a max return record count of 50k, I get back zero results.
I now decided to test against 100.4, and I get the same exception mentioned above. The size of the shape does not seem to be the problem. My original shape has 900+ rings and this fails. When I attempt an overlap with the extent of this complex shape, I get back results the 50k max.
I am happy to share the service I am testing against, as well as the geometry in question, but this will need to be in a private forum due to it being sensitive data.