>Satellites have hard time taking pictures of every square mile of a sea to find any ship, yet alone the one you need.
That's why satellites use radars and scientific instrumentation magnetometers to find stuff like ships or even subs underwater.
Those suffer from the same problem. There's a lot of ocean, and if you don't know where to look then you won't find what you're looking for.
There might be some secret technology that we're unaware of but as far as we know magnetometers can only be used to detect underwater targets at very short ranges. I highly doubt that they're used on military reconnaissance satellites.