Nods, yep cache it.
Still, even then it sounds like a usability nightmare, a drop list that must contain so many options it times out!
Probably needs an ajaxian-style autocomplete, say after 3 first letters have been typed.
This looks like one of those tasks where you really need a real end user to show you exactly how they would use this tool in real life. How they filter and sift so many options in their heads will be unlikely to match your modelling of their processes.
This is the most annoying thing I find about most kinds of contract work, eliminating the levels of bureaucracy between you and the real end user merely in order to create something useful and usable.