I got a 5.9 short block from a local pull-and-pay for $125, didn't need the heads since I already had some as well as an air-gap carb intake. I couldn't check the mileage since it was a 2001 Ram 1500 with the digital odometer and the wiring was trashed but the inside looks fantastic; no sludge, no cylinder ridge, very little varnish... might check some bearings to be sure too.
That LKQ thing sounds like the way to go though if you have one local, would have tried that before but I got a good one anyway fortunately.