you have a common problem here. the fadal machining centers you have purchased are certainly commodity machines which can be had at an inexpensive price compared to other machine tool builders. the old saying "you get what you pay for" fits the bill here. my experience has been that when looking at machines, price should not be your number one determining factor in buying the equipment.
let us look at the facts. you machine stainless steels mainly. also, your applications require that you take "fairly heavy milling" cuts. the fadals you possess, like most fadals i have seen, are belt driven. this type of drive does not lend itself well to the type of machining you wish to do. the machining of stainless steels requires a lot more torque and horsepower than say mild steel or aluminum. direct drive or geared heads work best in these applications. the direct drive is certainly the most efficient drive versus the geared since you do not have a gear train to work through. however, the geared head can provide the most torque at times. this can really pay off when taking heavy milling cuts in stainless steel. you need to take a look at the cutters you will be using the most. the bigger the milling cutter the more power required of course. i strongly suggest that you make a list of the tools you will use the most and what rpm's these tools will run at. at that point, you should try to figure out the horsepower required to drive each tool at it's proper feed and speed. then, i would look at the horsepower and torque diagrams of the prospective machine tools. you would be surprised at how many people over look this. you should use this information to help you narrow down your selection. also, i would strongly suggest a CAT50 taper spindle over CAT40. it is amazing how much rigidity you gain by doing this. it is a costly option, but through the spindle coolant and through the spindle air blast are valuable to have. a lot of people blow these options off as being too costly and that they can live with out them. however, this is a misnomer. these options can save you a lot of time and money - take it from someone who has done it both ways. you asked about box ways or linear guides. i would suggest going with the box ways in your application. this will provide much more rigidity for the machining of the materials you seek to mill. you may loose some rapid traverse speed, but you will easily gain this time back with your increased feed rates during milling. you normally see linear guide machines more applicable in high production, aluminum machining scenarios.
wih only 100k to spend, you certainly could not afford a new machine with the specifications i have listed. however, i would suggest that you seek a used machine in good condition. you can normally find these from the main machine tool builders (mazak, mori seiki, hitachi seki, monarch, etc..). also, i have talked to people who have had good results with haas. one friend in particular machines a lot of A2 tool steel for making brake shoe dies. he loves his machine and has had it for three years. you asked about the service. this is a delicate issue in that some people get good service from a machine tool builder and another person claims to get bad service from the same maker. i would suggest that all the service stuff is made clear in the beginning and that everything is in writing and that both parties have copies. in case you do have a service problem that goes unanswered and is covered in your contract, you will have some sort of a leg to stand on.
good luck and good hunting.