Before adding more parts to your car, have you run a jumper to your fan? You mentioned that the fan comes on with ac, but there are 2 fans and only one is in the ac circuit. Have you run a jumper from the battery to the other fan to make sure it works? In case one of the switches breaks ground make sure that you use 2 jumpers, 1 to the positive for the fan the other to the ground side. From there trace power back from the fan with the engine at temperature. Testing for power should locate the exact place where you are losing power. Even though you replaced switches and sensors, it would not be the first time that one was bad out of the box.