"CompleteDate" not working as search filter

[udayogra]

I am trying to create a task and set it as completed with some past date. This is how request looks like. CompleDate is in 2006
<t:Task><t:ActualWork>0</t:ActualWork><t:CompleteDate>2006-04-10T07:00:00Z</t:CompleteDate><t:PercentComplete>100.0</t:PercentComplete><t:Status>Completed</t:Status><t:TotalWork>0</t:TotalWork></t:Task>

Now I am using search filter to search tasks which completed between 2001 and 2018(current time). This is how reauest looks like

<m:Restriction><t:And><t:IsGreaterThanOrEqualTo><t:FieldURI FieldURI=""task:CompleteDate"" /><t:FieldURIOrConstant><t:Constant Value=""2001-04-09T07:00:00Z"" /></t:FieldURIOrConstant></t:IsGreaterThanOrEqualTo><t:IsLessThanOrEqualTo><t:FieldURI FieldURI=""task:CompleteDate"" /><t:FieldURIOrConstant><t:Constant Value=""2018-04-02T16:00:00Z"" /></t:FieldURIOrConstant></t:IsLessThanOrEqualTo></t:And></m:Restriction>

I am getting empty result. Am I missing anything?

If I set current time as some future time like 2019, I get the results.

This happens with Exchange 2013 but works with 2010