Hi Shel
I agree with what's been said to this point, that the people who run, operate, and maintain the machines are more important then type of machine or brand of chemistry or paper. I was a bit surprised at the problems you were having as they are more common with roller transport then dip & dunk.
As to questions you could ask. What their maintenance schedule is and what they do for maintenance. Most labs use machines that use a uni-channel balancing system. Ask how often they balance and set -up that. You could also ask to see their machine plots. What you are looking for there is consistency. Daily changes should be small, 1-2 points, and the overall line should be relatively flat. My preference is to have the C-41 running between 0 and +5 on all 3 colors in LD, though that is not easy to obtain. Stain/D-min is the only one where minus is good.
Butch