Figure out a better directory structure for your media library and/or take the time to tag your files with usable metadata? Investing in a suitably sized NAS array so can have everything accessible rather than hunting through a bunch of external drives or whatever would probably help too.
My media library is a similar size, and I know from experience I can reliably locate specific files given a realistic set of criteria about what I'm looking for. If I know the date and location of the shoot it'll take seconds, and if I'm searching on keywords for what's in the file, then maybe a few minutes to whittle it down.