If the dates are not the real dates, the sorting will work as it should work because it will sort the text not the numbers.
Excel treats dates as real numbers so if your dates are not real dates, convert them into the real dates and then apply the custom formatting to the date as per your customer's requirements so that the dates in the cell will appear in the desired format but underneath the cells, the date will remain the real dates and you can sort the date column properly as well.
To know whether a date which looks like a date is real date or not, you can check it with the function ISNUMBER. e.g. if your date is in B2, in a blank cell, place the formula =ISNUMBER(B2). If the formula returns True that means the date in B2 is a real date but if the formula returns False, that simply means the date in B2 is a Text string which looks like a date but not a real date.