It's got to be because of the conversion of the dates to strings. Just leave them as dates. Use date math and date comparisons within T-SQL. They work. String manipulation instead of using core data types frequently leads to problems.
"The credit belongs to the man who is actually in the arena, whose face is marred by dust and sweat and blood"
- Theodore Roosevelt
Author of:
SQL Server Execution Plans
SQL Server Query Performance Tuning