I'll tell you exactly what the issue is, since nobody seems to understand what is going on.
When they moved all the threads, they did so doing in the 'hard move' way. (Basically, moving the threads, but not updating the search indexes in the DB. vBulletin does this automatically when a moderator uses the 'Move Thread' option in the inline moderation, or Mod CP)
There's a very simple solution, but only Admins can actually carry it out.
Admin CP -> Maintenance -> Update Counters -> Run the stuff related to threads, posts, and search indexes. (There's 6 or 7 IIRC. I don't have an ACP open atm, so I can't check.)
Edit: opened up ACP just to give a list of stuff to run:
Rebuild Thread Information
Rebuild Forum Information
Rebuild Search Index
Rebuild Post Cache
Rebuild Statistics
Rebuild Similar Threads
Update Post Counts
Remove Orphan Threads
Remove Orphan Posts