A supergrid is 5000 by 5000 tiles.
Prospecting scans a radius of 1000 tiles around your character.

The circles represent the area scanned, and the dots are the location a character is standing when they use the rustroot extract. It should take 18 units of rustroot extract (1.8 litres) to check an entire supergrid for mines. You could do this systematically by simply counting how many minimap tiles passed, once you’ve found the corner of the grid.
Prospect, walk east (or west) for 16 minimaps, prospect , walk 16, prospect.
Walk 8 more minimaps, then walk south (or north) 8 minimaps.
Prospect again, and start working your way back west.

Checking an entire supergrid for mines should only need 5 units of raw rustroot (and a lot of free time). Any village larger than a couple of people probably has enough to do it in a cupboard somewhere. Once you’ve actually found a mine you need a lot more to zero in on it, of course.
I thought rustroot was rare at first, but once i got my explore a bit higher I haven't had a problem finding it. Does anyone else get the impression that there's a little bit too much rustroot available compared to how few mines are in the world? Even a new supergrid could be easily be swept for every mine on it within a week.
Update:
Regarding caves, Thurrok adds that unless a cave is deeper than 1000 tiles you should only need to prospect once inside the entrance to check it. Cave mines won't be detected from outside, so you see a cave on the way peek inside and use the rustroot extract.