To given an update here after debugging this. It turned out the server is just very slow to respond sometimes due to disk I/O being slow. There is no real solution besides increasing timeouts, which may cause all kinds of other side-effects.
The error reporting inside the minecraft admin webui could be improved to give more indication besides internal server error though, have to see when I find time for this though.