a couple of (sometimes overlooked) things first.....
when did you last apply Windows Updates / reboot the server?
Do you have RAID mirrored Hard Drives? Are they both still operating correctly or do you have a drive failure or is it rebuilding the array?
When was the last time you defragmented the server drives?
How much free disk space does the server have on it's Windows Drive? Has it run out of space to run the operating system happily?
Check in Windows Task Viewer, is something hogging all resources on the server?
Have you added any new PC's to the network? Is there more network traffic that could be causing a slowdown?
Where are you searching? if it is the "find" on the audiowall, then it is looking through the cart list files on the server.
If there a lot of audio above 10,000 then the single file that holds this information can be slower to search through.
If you are searching in the database tab, then yes a compact / repair is something to try - also check to make sure you are not leaving weeks / months of old scheduled log in the system (settings can be changed in Autotrack).
To compress / repair http://forums.broadcastradio.com/2728/Compress-Repair-a-Database-in-Myriad-v3
You also say that it is Myriad v3.6.3 - you really should upgrade to v3.6.6 which is the final release of v3 - or talk to us about the possibilities of upgrading to a newer version.
Broadcast Radio Ltd