I think the best method is to use a microflow in your published webservice where it now does a Find or Create.
That way you can do all your validation and assocation setting straight away.
Just do the validation in the microflow that's published. If you want to abstract it away a bit, you can call a subflow as the first activity in the microflow and do all validation there.
Alternatively, just add either validation rules or a before commit microflow.