It wasn't that both parents had tried desperately to find their daughter.
Literal
Parents [subject-が] two-people both daughter [object-を] find-try-to desperately effort did [it-wasn't-the-case-that-わけではなかった].
わけではなかった is the past tense of the partial negation — 'it wasn't the case that both had tried hard.' 懸命に (desperately/earnestly) emphasizes the intensity of effort. The sentence implies one parent was less committed to the search.