First off, I recommend doing this on the buddy server first. This will not affect your primary server when you do so.
Go to Computer management and choose Services and Applications. Then look for the Indexing Service. Highlight the Indexing Service and make sure that there are no Docs to Index. Then go to F:\NOM and find indexdel.exe Double click this and there will be a message confirming you want to delete the index. Say OK and the Index will be deleted. Go back to computer management and look at the Docs to Index. It will begin climbing. The system will re-index everything in ENPS and you will not be able to search for anything during this time.
After it has finished (several hours later) switch to your buddy server and see if your search times have become very quick again. If so, repeat for the process for the primary server. Remember to keep everyone on the buddy so that they can search normally while the primary is being re-indexed.
If this doesn't fix it call ENPS.