If you’re allowing users to enter dates as strings, then that is just asking for trouble.
My first bit of advice would be to avoid that if possible, and use a date picker.
If you don’t want to do that, then my suggestion would be to use a math column to convert the entered “dates” to integers, and then work with those. Use the following:
Year(Date) * 10000
+ Month(Date) * 100
+ Day(Date)
The math column seems to be pretty good at dealing with dates as strings, so you might have better success with that.
The last thing I would use in this situation is the Format Date column. I gave up on that many many months ago, and I just don’t use it at all now. I wrote a bit about why below: