I tried deactivating all the plugins. This did not work. I also tried resetting the plug ins folder by FTP and resetting custom permalinks back to default setting.
The issue has to be something with Windows Server. We first had the site hosted on a Linux and since moved it to Windows. On Linux the search worked just fine.