I have a very unconventional recommendation for you. You can pick up this scope for $150:
http://www.adorama.com/CNC90N.html (also at
http://www.amazon.com/Celestron-52268-C90-Mak-Spotting/dp/B0038QYRDO)
The eyepiece it comes with gives you 38x power. You can then buy this eyepiece for $40 and have just over 31x:
http://www.adorama.com/CN40O.html Eye relief is quite good with this eyepiece.
This scope is a Maksutov-Cassegrain design. It is basically a mini-telescope, as usually the design is found on larger scopes. It consists of a series of mirrors to bend and focus the light, rather than pieces of glass. Dollar for dollar, a Maksutov-Cassegrain design will give you much better image quality.
I have exactly this setup, but with the previous generation Celestron C90. There have been many iterations/generations of the C90, and all have been very highly regarded. I honestly do not know how this current model stacks up, but I would be very surprised if it too was not an excellent performer. It also has an excellent no fault warranty. It also has an angled eyepiece, which is an absolute must, especially for any prone shooting.
The main downside to this design for range use is the magnification. You can't go any lower than 31x, which can be a little high if mirage is really bad. That said, many high power shooters use a KOWA 27x eyepiece/scope combo in all conditions and do just fine. The benefit of a Maksutov-Cassegrain is that it handles very high power with ease. Good luck seeing through the mirage though... Oh, and the scope is HUGE. Not heavy (almost no actual glass in it), but very large and unwieldy. And heavy rain may be an issue. The scope itself I believe is waterproof (not positive), but water may get in whatever eyepiece you use.
For a more conventional design on a budget, check out Konus. Very highly regarded as well.