Hello,
Could you specify if you are using a Home Page Action or the Search tab when the issue occurs?
In both cases search should not last that long. For example, the delay can be caused by Security Roles. For troubleshooting purposes, could you sign on to the Web Interface as default service administrator (specified during service installation), perform the search again, and provide us with the time frame?