1. You could convert your Rem 700 to anything from the '06 case size up to and including any of the RUM chamberings or wildcats. The list is nearly endless what you COULD convert your 25-06 Remington into. Only limitations are your goals and how much you want to pay to convert the receiver which even into a RUM class chambering is not all that difficult.
For the needs you discribe, there really is no need to convert to a larger chambering then the '06 case size. To be honest, for what you want to do, out to 600 yard deer hunting, I would look real hard at the 6.5-06 AI. A 140-142 gr match bullet such as the Berger VLD or A-Max or SMK will be extremely effective on even heavy deer out to 600 yards and perform very well in the wind and terminally as well. A 6.5-06 AI will pretty much do anything that a 280 AI will do but do so with a bit more velocity(less drop), matching wind drift and noticably less recoil then the 280. Either will certainly work but the 6.5 will just be a bit more warm and fuzzy to shoot.
2. Simple rebarreling will range from $300 to $600 depending on barrel cost and what the smith charges for barrel fitting and chambering. Personally, I would charge around the top end for a 27" stainless steel Lilja, installed, finished and bead blast matte finished. Most on this board will be similiar to this with equal priced barrels.
Thats for a simple barrel installation. It can get much more extensive if you want full receiver accurizing and such. In my opinion, its a risk to install a match grade barrel on a receiver that has not been accurized. Much better investment to know that the receiver is true and square when the barrel is installed. Not saying the rifle would not shoot, just the odds are much better if the rifle is true from the rear receiver screw to the muzzle crown.
3. I would support the smiths here on Longrangehunting. Not saying myself specifically but I know most of the smiths that frequent LRH and all are top knotch guys and smiths. You will not go wrong with any of us. I only say to use a smith here on LRH because you seemed to feel the opinions here were worth asking your questions to. There are hundreds of great smiths in our country so the smiths here are certainly not the end all but they are great smiths and put alot of time and offer alot of free experience here on LRH so we appreciate the members support.
4. I use Lilja, Hart, Broughton, Rock, Krieger, Brux and Bartlien mostly. Of these, by far I use Lilja the most but all of these will get you a 1/2 moa rifle if installed properly. From what I have seen, on average, you can really take your pick. They are all very good.
Some of the lower priced barrels such as Pac-Nor, Shilen and Douglas will also make good shooters but they are not in the class of the other barrels mentioned previously.
Hope this helps some. Good luck with your project.