Autocomplete rule for Address Change Date Validation

We have a rule that restricts employees from entering a past dated address change. When an employee enters a past dated change, we are seeing that the rule shows an error as expected. However if the user changes the date after clicking OK on the error message then we get a different error on the Effective Start Date field. If he tries to Cancel out of the Address Change then no action occurs and the address change is not cancelled. Has anyone had success implementing a similar rule?