What makes flight recorders harder to find than tagged sharks?
They're different usage cases, and have to be engineered differently. Three major points:

A shark tag doesn't have to survive a 500mph impact (#7 on the list) with the ground, and a flight recorder has to be able to do so. It adds a lot of padding and weight, and limits the kind of battery that can be used.

Sharks also don't dive to a depth much greater than 3000 feet on most occasions. A planes flight recorder is designed to survive to a much lower depth, under much larger amounts of pressure. Not to mention being designed to survive all sorts of other things.
Another point regarding depth, it is much harder to search for a signal at a depth of 15,000 ft, than it is even at a depth of 5000 ft. This article shows how big of a difference you get between even 20 meters and hundreds of meters (not thousands), it gives a good idea of what I mean.

If a shark tag fails, nobody cares. If you tag 100 sharks and 30 of the tags survive, you still have some pretty good data. But if one airplane crashes and its black box fails, it's considered unacceptable. They are required to survive 100% of the time.


All of these differences combined mean that black boxes are manufactured to much higher standards, and as a result they are bulkier, have different sorts of radios and require much more battery life (to support the larger systems) than a shark tag. All this conspires with the difficulty of getting a receiver deep into the ocean to make finding FDRs/CVRs really difficult.
That's not to say they couldn't design one that is much better, it just becomes extremely expensive (as all things are on airplanes). And you have to determine if these edge cases (like flight MH370) are worth making an airplane a few million dollars more expensive (between R&amp;D and certification, the later being quite expensive).
I think the theory was they should be able to find any one of these within a month, and that may take some rethinking (maybe 3 months, or a year perhaps?) But they'll never be as successful as shark tags just because the requirements to be able to find one at that depth 100% of the time are quite different from the needs of a shark tag.