We had the same problem. We created sub directories with no more than 300-500 images in each. Luckily though, the names on ours also contained numbers so that we could easily move them around into the subdirectories and make it easy to find them when we went to relink. If you have a more generic naming pattern or if the names are all over the map, then you may have more of a problem.
Maybe a solution (if the names are all jabberwockied or there is no rhyme nor reason to them) is to have it set up so the images go into subdirectories based on the date they're received. That way, when new jobs come in, they're dumped into a folder with that date within your directory. May make them easier to find if you know what date the job comes in.....
