Re: It is a waste of time
We had a FAR better idea of where the Titanic went down and it still took nearly a century to find - and the Titanic is a lot bigger than a plane and went down in only two pieces instead of thousands that would be spread across a very wide area.
Yes, but we have better tech now. For instance, an Autosub 6000 can run off autonomously for 3 days at a time and run a multi-beam sonar survey to 1m resolution or better (depending on how fast you want to survey - resolution-vs-coverage).
But it's still a major undertaking - back of a napkin maths suggests you'd need ~200 such missions to cover 25,000sq.km. That's 600 survey days, which probably accounts for ~800 days at sea including turnaround, battery replacement and returning to port for provisioning/crew change. Of course if you were able to deploy 3 such subs from a single ship with minimal overlap (and tow a fish behind the mothership as a 4th instrument), then you could get the total mission time down to about a year. So that's quite quick by comparison, but tying up an entire vessel for 12 months is costly, though you'd hopefully be able to pad it out with some unrelated science whilst cruising between RV points.
Or you could do the inverse which is to dedicate 2-3 autosubs to the job and place them on vessels of opportunity - doing a cruise into the target area? Could you take this, throw it in the water near sector #137 and pick it up three days later? Ta.
It's certainly possible to continue the search fairly cheaply by piggy-backing off existing cruises and research. The deep ocean is fairly poorly mapped (to less than 1km resolution anyway), so hi-res sonar surveys have a scientific value in and of themselves.