In my case, I think I am coming to the crux of the matter. The GP-Service has an associated Map-Service to display the results. The jobs directory of the GP-Service is configured to never clean up the results, so that the app can always view them via map service.
I discovered that the map service never frees up his memory, so the ArcSOC process on ArcGIS Server is using more and more memory. When the soc reaches 800 MB of memory, it stops working and responds with errors. The only way to get back to normal is restarting the service and thus freeing the memory.
I am currently working on the issue with Esri Germany Support.
Btw, this problem occurs on ArcGIS Server 10.2, but I think 10.4.1 does not show this error.