Did you look at the form layout for the field and see if it's marked required there?
Yes, and it is not checked as mandatory.
Validation rule might come from other object as well, if having for example some custom trigger implementation between Incident and some other objects. So please check which records could be updated based on inc update.
Other than going to the object and doing a 'find on page' from the browser, I don't know how to search validation error messages.
I am curious, on your specific error message, if you can duplicate this in a sandbox? If so, does it repeat regardless of what category you are using? If you can, would you be willing to take a screen shot(s) of the page? What if you remove the Service field from the field set as a test. Do you still get the error?