Sounds like the install is under sized for what you are doing.
Fuse holders and fuses should not melt at all. Sounds like the setup is running right at 24 or 25 AMPS, and some heat caused either by current inrush or under sized wire is working against you.
What size wire are you running ?
The circuit should be sized so it is 80% of the max load.
If the fans draw 30 Amps, that is 80% of what the circuit needs to be sized for, so a 37.5 Amp setup is the minimum. This means you should have a 40 Amp relay, and a 40 Amp fuse.
Also wire size plays into this, so if the above is true, that would mean 8 AWG automotive wire ( 105* C temp, not the 90* C THHN at home depot ).
If the fans are 25 AMP, you should still stick with the 40 ( or higher ) relay, that has a higher cycle count on it ( data sheet will show this value ), and run 10AWG wire both ground and power to make sure you are not choking it.
Also, only good solder splices, no butt crimps on this install ( those add resistance to the circuit ).
Sounds like it is time to start over with the install.