Hi methodman,
First, sorry for the late reply, but your thread fell by accident in the less-priority queue.
Back to your question: In my opinion this is not strictly a validation rule, but of course it can be. I would implement both ways (fetch to validate and then catch if something wrong happens) because there are some scenarios when only fetch-to-validate could be tricky. Imagine that while your application is validating the existence of the record, another user save the same data. In both cases, you always have to catch to see if something went wrong and inform that to the user.