onetrack,
Excellent summary of the problem.
The amplitude of a magnetic anomaly created by discrete ferrous mass (the steel in an engine for example) varies as the reciprocal of the cube of the distance (1/R^3), so you need to be very close to the object to detect it.
Here's a table of typical detection distances from the Geometrics website posted by onetrack:
Typical Detection Range For Common Objects
Ship 1000 tons: 0.5 to 1 nT at 800 ft (244 m)
Anchor 20 tons: 0.8 to 1.25 nT at 400 ft (120 m)
Automobile: 1 to 2 nT at 100 ft (30 m)
Light Aircraft: 0.5 to 2 nT at 40 ft (12 m)
Pipeline (12 inch): 1 to 2 nT at 200 ft (60 m)
Pipeline (6 inch): 1 to 2 nT at 100 ft (30 m )
100 kg of iron: 1 to 2 nT at 50 ft (15 m)
100 lbs of iron: 0.5 to 1 nT at 30 ft (9 m)
10 lbs of iron: 0.5 to 1 nT at 20 ft (6 m)
1 lb of iron: 0.5 to 1 nT at 10 ft (3 m)
Screwdriver 5 inch: 0.5 to 2 nT at 12 ft (4 m)
1000 lb bomb: 1 to 5 nT at 100 ft (30 m)
500 lb bomb: 0.5 to 5 nT at 50 ft (16 m )
Grenade: 0.5 to 2 nT at 10 ft (3 m )
20 mm shell: 0.5 to 2 nT at 5 ft (1.8 m)
Note that you have to be within 30 m to detect an automobile. Even if you could find a magnetometer to operate at depths in excess of 5000 m, these detection distances are incompatible with the track spacing of the sonar survey that is currently underway.