Paulinus,
When I was in Oberlin KS shooting P'Dogs the farmer was telling us that the 25-06 was the weapon of choice around there and was good to 500 yards if you did your part. I started looking for one and ran into a 257 Wby for a great price and have been very pleased with it, except for the cost of factory ammo.
I found that it liked the 115 grain Barnes X-bullets the best and Weatherby lists their retained energy at 1359 ft*lb at 500 yards - way more than any deer needs to convince it to quit living! (Sierra put a more conservative 1100 ft*lbs out for their 117 grain boat tail at 600 yards, but still more than enough) I found that on a realitvly calm day I was hitting a clay pigion about 1/2 of the time at 710 yards, again good enough to convince a deer to give up. I feel very comfortable out to 600 yards and if the wind was calm I wouldn't pass on an 800 yards shot.
No matter what you choose, good luck and remember to practice, especially in the wind. The wind is a bigger problem than distance.