Without getting into the mess of redesigning existing Flight Data Recorders, I have a simple proposal that I think would help in deep water crashes.
I propose that several floating cushion sets be distributed around the plane (tail section, along fuselage, etc.). These FDR floaties would be about the size of a seat cushion, but they'd be wrapped in a water soluble cover. When a plane crashes into the water, if the plane breaks up, then several of the cushions would float to the surface. When the cover dissolves, several folded arms open up making it much bigger exposing a orange-nylon covered mesh with an aluminum sheet embedded. This would be easier than seat cushions to see from satellites and planes, and the aluminum layer would reflect radar and make it easier to find.
This alone would help find water crashes sooner, but if you add a simple USB memory stick in the center, then have data similar to the current FDR's being fed into it, then finding one of the floaties would give quite a bit of information including the final GPS coordinates before the crash.
These devices would be light and cheap. I'd think current planes could be retrofitted very cheaply. The only challenge would be the wiring needed to connect to the main FDR or the nearby data splitter. But just putting a few in the tail section alone would end this madness of having to find FDR's on the seabed to get a better idea of what happened.
Wouldn't this be easy to implement without disturbing current FDR use and development? These would be destroyed in a fiery land crash, but that is not their purpose. This is just so we can find plane crashes in the sea when we don't know precisely where they went down (and to get basic data when the black boxes are too deep to get to immediately). Malaysian flight 370 and Air France Flight 447 would have both been greatly aided if these floaties were in those planes. What do you think?