I took a few days and wrote something to do this. It was not really as straightforward as I was expecting so I'll share what I learned.
What was hard
Here are the major headaches I encountered.
Dealing with JPEG Compression Artifacts
When sampling the values for the legend, I encountered many JPEG compression artifacts. This required me to apply a median filter. The median filter width needed to be a parameter of the function (needs different values depending on how big the legend is.)
Dealing with "bands" in the legend
The legend in your first example is divided into discrete sections (bands) and the numeric quantity desired is probably the middle of the range that the colour spans. For example, the left-most box covers values from -6500 to -6000 and should probably return "-6250" when trying to sample a single colour of that value. Also, consequently, no pixel will return the value "0". There is no colour representation for "0" (in that first map anyway.)
Dealing with differences in tone / value.
Sometimes the exact colour in the map doesn't exist in the legend, especially due to the text labels, so you have to do a "closest" matching algorithm and the hue seems to be more important than the value (black&white-ness) so it was better to evaluate "distance" between colours in a colourspace other than RGB.
Text overwrites data
There are plenty of black pixels in the map due to the labels, but these need to be ignored somehow. It makes sense to try to infer what the value behind the text is, and only colours that are not in the legend qualify for this kind of inference.
Manually selecting points on the legend is not precise
Each time I eye-balled it and manually found a point that looked like approximately the end-point, I'd choose a slightly different pixel, resulting in slightly different values between attempts. Perhaps a snapping technique would be better where I could "hint" where the legend is, but it would find the high-contrast edge markings and snap the hint point to the exact point.
Most maps don't have continuous legends.
Most other images that I went searching for with test data had discontinuities in their legend (discrete boxes of colour) as opposed to a nice continuous linear gradient like you provided. This makes it extra difficult to automatically come up with the mapping from colour to value just by analyzing the positions of the colours in the legend. I was disappointed when trying to apply it to most maps.
It was very useful (especially while debugging) to visually show the point on the legend that it thought best corresponded to the colour being picked in the map.
It's useful to persist the location of the endpoints of the linear gradient portion of the legend and the values that are associated with them between runs of the application. Don't underestimate the value of this. It's annoying to have to specify all that stuff every time.
What worked well
Represent the legend as all the pixels along a line segment
Specify two (x,y) locations of the start and end of a linear gradient (the legend) and manually define the values that are associated with them.
build up a discrete sample set for the gradient
Sample all the pixels in between the start and end points to build a linear gradient dataset.
Apply a median filter to the linear gradient dataset to filter out JPEG noise.
Quantize the dataset to locate centroids
Optionally filter out bands (long runs of samples in the linear gradient dataset that have approximately the same colour) and replace them with a single sample at the centroid (average position).
Use bilinear sampling when picking a pixel
Pick a pixel in the map and perform a bilinear sample to smooth out pixellation. This seems to help improve the smoothness and resolution of the map.
Linear search is fine
Linearly search for the data point in the linear gradient for the closest colour. For an interactive picker working from mouse clicks, you have lots of time to perform a linear search. No fancy hashing, indexing or optimized searching was required.
Hue is important in the colour distance function
Compare distance between colours using a distance function in a colourspace that tolerates brightness difference more than hue difference. (like YUV, for example)