As we found with MBS-12971 the cdtoc search will only try to find appropriate mediums in the first 300 releases matching the given name. While improving that properly is more work, at the very least we should have a message that notifies the user that their search should be as specific as possible and why. Something like this sounds good to me:

"No results found. For performance issues, this search checks only a limited amount of releases closest to your entered query. To ensure a better result, search for the full release title or as close to it as possible. You can also {search_link|search manually} and paste the link to the release here."