You have these options, as I see:
A. Try to fetch a copy of the entity, and see if it return something (the IsNew property will be true if it has been deleted). Then if it exists, delete it.
B. Perform a DeleteMulti specifying the correct filter for that ID. That wont fire an exception and will let you know how many records had been affected (1 or 0).
C. Do what you are doing. It's not that bad. You don't know if someone else deleted it, so you should trap any exception and do something with that (notify to the user, etc.).