I did a little research on your error and saw that it was based on the parsedatetime function of joda. On their site they state that they use the ISO8601 standard which is equal to yyyy-MM-dd or 2000-02-15 in your case. For more info please take a look at wikipedia
However, i would still recommend you to use microflows over validation rules. Also see my comment on your op ;]
I would use a Regex for this. You can use the community commons module to test a regex in a microflow. What microflow did you use for the validation?
I would suggest not to use the default validation rules as they are applied at all times and can sometimes be confusing, especially since they also trigger on refresh of you object.
Then create a custom save button that checks the following:
$inputObject/Date => parseDateTime('01-01-2000', 'dd-mm-yyyy')
If true then you continue to save if false then you stop and do nothing.
If you want to warn the user beforehand you set a onchange microflow that basically does the same check if true it does nothing if false you present the user with validation feedback and optionally clear the date.