The cost usually goes up very quickly as the frequency of the scope goes up,
so that is one of the key things to look at when judging the value.
You always need more bandwidth than the signal you are trying to observe.
6 and 12MHz clocks are common on early 80's boards so yes 20-40MHz is
the minimum (I have 20, 40 and 100MHz analogue 'scopes, you pay for
the higher end but all these will give you important debug information).
Don't worry if the 'scope doesn't come with probes, you can get these
individually and the connectors are surprisingly standard. Ideally get
probes that are x1/x10 switchable (or fixed x10). If it comes with
decent probes then all the better.
I always look for a 2 channel X-Y capable 'scope with a 3rd 'Z' channel on
the rear to make it a little easier to debug vector boards (but even without the
Z channel you can tell if a vector board is working).
Personally I'd pick one that shows a working trace pattern in the photos
(I'm not sure about things marked as "not tested" as it's not too hard to
turn a scope on and show a calibration trace or even a flat-line trace).
I paid 50 quid for a perfectly adequate 20MHz 'scope on ebay
not too long ago so you don't need to pay the earth.