I've had some rather large libraries at a few of my employers and that initial search can certainly slow things down. Do you have a large library? Do you have a long list of libraries setup in your Library Manager? Try removing some of them. When doing a serch for a part limit yourself to one library at a time instead All Libraries. Don't just search with a wildcard "*", instead use an expected character with the wildcard like "*res* for a resistor. These are suggestions that will speed things up.
There are possibly multiple issues.
Ever since the VeriBest days (if you are talking Expedition PCB, not PADS) forward annotation has always been VERY slow over a network compared to having the library on a local drive. From network tracing I have done this appears to be at least partially due to inefficient data accessing combined with no data caching. (The operating system will cache local drive data but not network data.)
In more recent years we have had problems with strange, random delays (up to a minute on occasions) when accessing our network-located library, whether it be from the schematic or from Expedition. It happens much more on some workstations than on others. Recently we have discovered that the delays are effected by which network switches are in the path between workstation and server. e.g. change a user from a 1G switch to a slower 100M hub can almost completely eliminate the random delays. The interesting/strange/worrying thing is that these apparently network-related problems are not evident in any other software we use - and we do company all work on network drives, nothing local.
It can be a major frustration at times, but it is not until you compare it to a local library that you realise how bad it is. (We don't do the comparison which is why users tolerate it.)
Thank you both for your replies. I have noticed the best improvment's come when we limit the number of libraries in the stack. We have come to use just a few client / house libraries full time and load others as needed. For the last few weeks we have been running smoothly and I will report back any additional changes.