Cooling Issue

If you try the solid mount fan, it might answer all your questions. Maybe the fan clutch is failing. Do you have the spring in the lower hose? How about the seal that seals the hood to the radiator?

The clutch is brand new, so I hope it's not failing. Is there a way to test it?

Yes, there is a spring in the lower hose and yes there is a seal on the hood (front and back)