Hi Martin,
How large is the feature class you are trying to edit (i.e. 10,000 features)? Also, would you be able to create a test feature class, save it in a new MXD, publish the MXD to server and see if you can reproduce this error? I'm wondering if it's something specific to your configuration or something with this specific feature class/service.
Thanks,
Jake