If the data source is from a stored procedure, return the date as two columns in the dataset. One is formatted (varchar) and another is in the Date time data type.
Say the stored procedure returns the colums : COLUMN_STRING_FORMAT and COLUMN_DATETIME_FORMAT
In the markup for grid,
<asp:BoundColumn DataField="COLUMN_STRING_FORMAT" SortExpression="COLUMN_DATETIME_FORMAT" DataFormatString="{0:dd-MMM-yyyy}" />
<asp:BoundColumn DataField="COLUMN_DATETIME_FORMAT" Visible="false"/>
Note the Sort Expression in the first line. It refers to the column in DateTime data type.
This worked for me when I was sorting on date in DD-MMM-YYYY format.