Assuming that, notwithstanding the reasonable doubt put forward in VoiceOfUnreason's answer, the business rule has been firmly decided on, as your question assumes.
Then the simple answer is that no system should trust its input, especially (but not exclusively) when the input comes from a human user.
So validate on every level.
If you persist your data, you should implement this check in your data model and deal with exceptions in your DAL (data access layer). From there, you can throw exceptions to be caught by your BLL (business logic layer) that uses that DAL.
Your domain layer should implement the business rule in its model as well. Sometimes the domain is generated at least in part from the data model, so it would automatically end up there. Again, you can throw an exception if the rule is violated.
Your WCF service can throw an exception too. This is widely considered a good thing, as long as you describe the possible exceptions your service may throw in your service contract.
Now you have protected your back-end from corrupt data, but it would mean you have to call your WCF service after user input, just to find out that there is an error. It is common practice to validate user input on the front-end without calling back-end services first, if such validation can be done based on the user input itself (checking for an existing user-name cannot be done like that of course, but checking whether a start-date lies before an end-date is common).
This you can easily do in the model in your application, using, for instance, data-annotations and validation. In this case, you provide validation messages that are meant to be sent to the end user.
Before submitting the user data to your WCF service, you validate the data, and if there is a validation error, your tell the user.