Lets say the plane is under water. With current radar and sonar technologies, we didn't find the plane yet. What if the paint coating or some other part contained markers which could be more readily tracked.

An example would be a floating accelerometer/gyroscope/barometer combination found on almost all phones for instance. If plane crashes, the markers will float and its path can be reverse plotted based on stored sensor data, which we will get when we find one floating around. It doesn't need to have internet connectivity.