Together with many other questions on this website tagged as 'homophonic-kanji', this is a case where in ancient Japanese when there was no writing system, there was no distinction among these words (i.e., they were a single word), but Chinese had finer distinction, and when Chinese characters were brought into Japanese, different Chinese characters came to be used to describe the same Japanese word depending on the context to match the distinction in Chinese. As a result, they came to be pronounced the same but written differently, and even after thousands of years, in native Japanese speaker's mind, it is often a subtle thing whether they are different words or not. People actually often do have problems distinguishing these, and there are dictionaries and software tools that assist you to distinguish them in kana-kanji conversion.
Quite often, there is a character that is used generally, this case
探 as you point out, which stands as the representative of the words in the group. The character for a specific meaning can usually be replaced by a character of the generic one, but not the other way around.
探 is taught at the sixth grade.
捜 is taught at the seven grade or later. In general, the kanji with the general usage is understood to be easier than the ones with the specific meanings.