I've just put on a new set of tyres. My tyres of choice are Shwalbe Marathon Plus, 700 x 32. In the photo you can see the new front tyre with the two I have just taken off. These two gave me 12,000km with no punctures. They're not exactly bald, but I'm doing a long trip and want the insurance of new casings.
The casing on the left, still with a couple of moulding dags, did 6800km on the back wheel, pulling a trailer and running two rear panniers, through central Australia to Brisbane and then back to Adelaide. I then swapped the front tyre (the middle casing in the photo) onto the back for the 5,000km I've ridden since then. These are classic tyres!
The photo at the bottom of the page is from 2011. It is a Specialized Armadillo (700x23) which had done 2000km only on the rear wheel, with touring panniers. Great for puncture resistance, but not capable of real distance. It was the last one I bought. I used cheap Cheng Shin Flatfighters for a while (half the price) but again, only good for a couple of thousand kilometres.