Solved! Go to Solution.
1. Most of the search issues were related to the incorrect date format being used as the string... MM/DD/YYYY was to be used.... (PJuster helped in the resolution)
2. IWA was not enabled on Exchange VD;
3. On the EV server, checked the EVAnon directory. IP address listed had an incorrect subnet mask listed. Removed the entry adding back only the IP address of the Exchange server instead of an IP and subnet
4. On the web.config file on the Exchange server, removed <add key="EnterpriseVault_WebDAVRequestProtocol" value="https"/>
All issues resolved.