I also vote to move this to the ASP.NET forum or maybe the general app development forum. This really is an application-layer issue--the sql bit is simple with stored procedures.
Insofar as what to do, it really depends on requirements. Inside the data access layer, I tend to have the objects figure out if they need to be inserted based on null or default id values.
The real trick you have here is how to figure out if those remote clients accessing your web service have the necessary permissions to update the records they wish to update . . .
Pfft . . . pfft . . . catching exceptions is NOT a way to handle business logic. They are very, very expensive items to throw and catch